Simple war scheduling algorithm in Java

Question

Let \$\mathcal{C} = \{ C_1, \dots, C_n \}\$ bet a set of \$n\$ different countries. We associate with each country \$C_i\$ with its potential \$P_i\$. We choose a specific country \$C_e\$ in \$\mathcal{C}\$. The battle operator \$B\$ is given as $$ B(C_i, C_j) = \arg\max_{c \in \{ C_i, C_j \}} P_c, $$ or, informally, it returns the stronger country among \$\{C_i, C_j\}\$, and its potential will reduce to \$\vert P_i - P_j \vert\$. We wish to compute such a sequence of battles that the remaining country has minimal potential, which would improve the probability of \$C_e\$ winning the entire war.

Below, there is my attempt and the algorithm runs in \$\mathcal{O}(n \log n)\$ time:

WarScheduler.java

package net.coderodde.fun;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * This class implements a war scheduling algorithm. In each iteration, two
 * weakest countries are selected, after which the two battle. The weaker of the
 * two cease to exist, but the potential of the winner country reduces by the 
 * potential of the weaker one before the battle. This iteration continues until
 * only two countries remain: the expected winner (chosen prior the war) and the
 * country that survived.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 9, 2019)
 */
public final class WarScheduler {

    public static final class Schedule {
        public final List<Battle> battles;
        public final Country remainingCountry;

        public Schedule(List<Battle> battles, 
                        Country remainingCountry) {
            this.battles = new ArrayList<>(Objects.requireNonNull(battles));
            this.remainingCountry = remainingCountry;
        }
    }

    public Schedule schedule(List<Country> countries, 
                             Country expectedWinner) {
        List<Battle> battles = new ArrayList<>();
        Queue<Country> queue = new PriorityQueue<>((c1, c2) -> 
                Float.compare(c2.getPotential(),
                              c1.getPotential()));

        queue.addAll(countries);
        queue.remove(expectedWinner);

        while (queue.size() > 1) {
            Country stronger = queue.remove();
            Country weaker   = queue.remove();
            Battle battle = new Battle(stronger, weaker);
            battles.add(battle);
            Country winner = battle.battle();
            queue.add(winner);
        }

        return new Schedule(battles, queue.remove());
    }
}   

Country.java

package net.coderodde.fun;

import java.util.Objects;

/**
 * This class describes a country.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 9, 2019)
 */
public class Country {

    private final String name;
    private final float potential;

    public Country(String name, float potential) {
        this.name = Objects.requireNonNull(name, "The country name is null.");
        this.potential = potential;
    }

    public String getName() {
        return name;
    }

    public float getPotential() {
        return potential;
    }

    @Override
    public String toString() {
        return String.format("[%s, potential=%f]", name, potential);
    }
}

Battle.java

package net.coderodde.fun;

/**
 *
 * @author rodde
 */
public final class Battle {

    private final Country winner;
    private final Country loser;

    public Battle(Country country1, Country country2) {
        if (country1.getPotential() > country2.getPotential()) {
            winner = country1;
            loser  = country2;
        } else {
            winner = country2;
            loser  = country1;
        }
    }

    public Country getWinner() {
        return winner;
    }

    public Country getLoser() {
        return loser;
    }

    public Country battle() {
        float potentialDifference = winner.getPotential() -
                                    loser.getPotential();

        return new Country(winner.getName(), potentialDifference);
    }

    @Override
    public String toString() {
        return String.format("[%s(%f) > %s(%f)] -> %s(%f)",
                             winner.getName(),
                             winner.getPotential(),
                             loser.getName(),
                             loser.getPotential(),
                             battle().getName(),
                             battle().getPotential());
    }
}

Main.java

package net.coderodde.fun;

import java.util.Arrays;
import java.util.List;

/**
 * Implements a demonstration of a war scheduling algorithm.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 9, 2019)
 */
public class Main {

    public static void main(String[] args) {
        Country expectedWinner = new Country("UK", 16.5f);
        List<Country> countries = Arrays.asList(new Country("France", 10.0f),
                                                new Country("Germany", 14.0f),
                                                new Country("Finland", 3.5f),
                                                expectedWinner,
                                                new Country("Russia", 27.0f),
                                                new Country("US", 33.5f));

        WarScheduler.Schedule schedule = new WarScheduler()
                .schedule(countries, expectedWinner);

        int lineNumber = 1;

        for (Battle battle : schedule.battles) {
            System.out.println(lineNumber++ + ": " + battle);
        }

        System.out.println("Expected winner: " + expectedWinner);
        System.out.println("Actual winner:   " + 
                new Battle(schedule.remainingCountry, expectedWinner));
    }    
}

Critique request

I would like to receive any critique: coding style, maintainability, readability, efficiency, to name a few.

Answer 1

• The comment

  In each iteration, two weakest countries are selected, after which the two battle.
  

  seems misleading. Correct me if I am wrong, but the algorithm select two strongest countries.

• It doesn't seem right to pass expectedWinner to WarScheduler. The expected winner is not scheduled for any battle, and the only thing the scheduler does with it is removing it from the queue. I recommend to prune it in main.

• A battle creating new country is an interesting geopolitical concept. In this case, however, making countries mutable seems more reasonable.

  In particular, since the scheduler already knows which country is stronger, consider a

  Battle Country::defeat(Country other)
  

  method, which adjusts the winner's potential. Notice that the Battle itself is now reduced purely to a historical record, and doesn't need to know intimate details of Country.

• An opportunistic optimization is to keep the running tally of the remaining potentials. Once it becomes less than the potential of the expected winner, the order of remaining battles does not matter.

Answer 2

The main thing that I don't understand is why you are passing the "expected winner" into the schedule at all. If it's not in the list, then it doesn't enter the queue, and doesn't need to be removed.