Sort with a Chain of Comparators

Problem

Every line is: name age score. Sort the lines by score from big to small. When scores are equal, the younger person (smaller age) comes first. When age is equal too, sort by name alphabetically. Print the lines in the new order, written as before. Build the order by chaining comparators (compare by score, then by age, then by name), not by writing one big if-else.

Constraints

  • 1 <= lines <= 10^4
  • names are lowercase words

Examples

Input

amit 20 90
zoya 20 95
ravi 19 90

Output

zoya 20 95
ravi 19 90
amit 20 90

Solutions

Best approachTime O(n log n)Space O(n)

Each comparator handles one rule, and the chain handles the tie-breaks, so adding a new rule is one more line. Java has Comparator.thenComparing for this. Python and JavaScript can sort by a key (tuple) or a chain function. The sort of Java's List and of Python is stable.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several lines.
 * Output  : The sorted lines.
 * Approach: Chained comparators.
 * Time    : O(n log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A Person keeps the three fields. Comparators decide the order.
        static class Person {
            final String name;
            final int age;
            final long score;

            Person(String name, int age, long score) {
                this.name = name;
                this.age = age;
                this.score = score;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        java.util.List<Person> people = new java.util.ArrayList<>();
        for (String line : lines) {
            String[] part = line.split(" ");
            people.add(new Person(part[0], Integer.parseInt(part[1]), Long.parseLong(part[2])));
        }
        // Step 2: Chain the comparators. The next one is used only when the earlier one says "equal".
        people.sort(java.util.Comparator
            .comparingLong((Person p) -> p.score).reversed()
            .thenComparingInt(p -> p.age)
            .thenComparing(p -> p.name));
        String[] output = new String[lines.length];
        for (int i = 0; i < output.length; i++) {
            Person p = people.get(i);
            output[i] = p.name + " " + p.age + " " + p.score;
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (1)
  1. Why does the second comparator run only for equal scores?