LeetCode-in-Java

2102. Sequentially Ordinal Rank Tracker

Hard

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

Example 1:

Input [“SORTracker”, “add”, “add”, “get”, “add”, “get”, “add”, “get”, “add”, “get”, “add”, “get”, “get”] [[], [“bradford”, 2], [“branford”, 3], [], [“alps”, 2], [], [“orland”, 2], [], [“orlando”, 3], [], [“alpine”, 2], [], []]

Output: [null, null, null, “branford”, null, “alps”, null, “bradford”, null, “bradford”, null, “bradford”, “orland”]

Explanation:

SORTracker tracker = new SORTracker(); // Initialize the tracker system.
tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.
tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.
tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.
            // Note that branford precedes bradford due to its **higher score** (3 > 2).
            // This is the 1<sup>st</sup> time get() is called, so return the best location: "branford". 
tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system. 
tracker.get(); // Sorted locations: branford, alps, bradford. 
                // Note that alps precedes bradford even though they have the same score (2). 
                // This is because "alps" is **lexicographically smaller** than "bradford". 
                // Return the 2<sup>nd</sup> best location "alps", as it is the 2<sup>nd</sup> time get() is called. 
tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system. 
tracker.get(); // Sorted locations: branford, alps, bradford, orland. 
                // Return "bradford", as it is the 3<sup>rd</sup> time get() is called. 
tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system. 
tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland. 
                // Return "bradford". 
tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system. 
tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland. 
                // Return "bradford". 
tracker.get(); 
                // Sorted locations: branford, orlando, alpine, alps, bradford, orland. 
                // Return "orland".

Constraints:

Solution

import java.util.TreeSet;

public class SORTracker {
    static class Location {
        String name;
        int score;

        public Location(String name, int score) {
            this.name = name;
            this.score = score;
        }

        public String getName() {
            return name;
        }

        public int getScore() {
            return score;
        }
    }

    TreeSet<Location> tSet1;
    TreeSet<Location> tSet2;

    public SORTracker() {
        tSet1 =
                new TreeSet<>(
                        (a, b) -> {
                            if (a.score != b.score) {
                                return b.getScore() - a.getScore();
                            } else {
                                return a.getName().compareTo(b.getName());
                            }
                        });

        tSet2 =
                new TreeSet<>(
                        (a, b) -> {
                            if (a.score != b.score) {
                                return b.getScore() - a.getScore();
                            } else {
                                return a.getName().compareTo(b.getName());
                            }
                        });
    }

    public void add(String name, int score) {
        tSet1.add(new Location(name, score));
        tSet2.add(tSet1.pollLast());
    }

    public String get() {
        Location res = tSet2.pollFirst();
        tSet1.add(res);
        assert res != null;
        return res.name;
    }
}