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
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.
/*
* 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)
- Why does the second comparator run only for equal scores?