2102. Sequentially Ordinal Rank Tracker
Description
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:
- Adding scenic locations, one at a time.
- Querying the
ith
best location of all locations already added, wherei
is the number of times the system has been queried (including the current query).- For example, when the system is queried for the
4th
time, it returns the4th
best location of all locations already added.
- For example, when the system is queried for the
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:
SORTracker()
Initializes the tracker system.void add(string name, int score)
Adds a scenic location withname
andscore
to the system.string get()
Queries and returns theith
best location, wherei
is the number of times this method has been invoked (including this invocation).
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 1st 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 2nd best location "alps", as it is the 2nd 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 3rd 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:
name
consists of lowercase English letters, and is unique among all locations.1 <= name.length <= 10
1 <= score <= 105
- At any time, the number of calls to
get
does not exceed the number of calls toadd
. - At most
4 * 104
calls in total will be made toadd
andget
.
Solutions
Solution 1: Ordered Set
We can use an ordered set to store the attractions, and a variable $i$ to record the current number of queries, initially $i = -1$.
When calling the add
method, we take the negative of the attraction's rating, so that we can use the ordered set to sort by rating in descending order. If the ratings are the same, sort by the dictionary order of the attraction names in ascending order.
When calling the get
method, we increment $i$ by one, and then return the name of the $i$-th attraction in the ordered set.
The time complexity of each operation is $O(\log n)$, where $n$ is the number of added attractions. The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
Solution 2: Double Priority Queue (Min-Max Heap)
We notice that the query operations in this problem are performed in strictly increasing order. Therefore, we can use a method similar to the median in the data stream. We define two priority queues good
and bad
. good
is a min-heap, storing the current best attractions, and bad
is a max-heap, storing the current $i$-th best attraction.
Each time the add
method is called, we add the attraction's rating and name to good
, and then add the worst attraction in good
to bad
.
Each time the get
method is called, we add the best attraction in bad
to good
, and then return the worst attraction in good
.
The time complexity of each operation is $O(\log n)$, where $n$ is the number of added attractions. The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |