#2102

Sequentially Ordinal Rank Tracker

expert · 1160 · lc hard +32 · 61.5% accepted · 407 likes · top 62%

Description

A scenic location is described by its name and attractiveness score, where name is a unique string and score is an integer. Locations are ranked from best to worst: higher score means better rank. If two locations share the same score, the one with the lexicographically smaller name ranks higher.

You are building a tracker that starts with no locations and supports two operations:

- Adding scenic locations one at a time.

- Querying the i^th best location, where i equals the total number of times the system has been queried so far (including the current query).

The test data guarantees that the number of queries never exceeds the number of added locations.

Implement the SORTracker class:

- SORTracker() Initializes the tracker system.

- void add(string name, int score) Adds a scenic location with name and score to the system.

- string get() Queries and returns the i^th best location, where i 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"]

Example 2:

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".

Code

class SORTracker:

    def __init__(self):
        

    def add(self, name: str, score: int) -> None:
        

    def get(self) -> str:
        


# Your SORTracker object will be instantiated and called as such:
# obj = SORTracker()
# obj.add(name,score)
# param_2 = obj.get()

class SORTracker:

    def __init__(self):
        

    def add(self, name: str, score: int) -> None:
        

    def get(self) -> str:
        


# Your SORTracker object will be instantiated and called as such:
# obj = SORTracker()
# obj.add(name,score)
# param_2 = obj.get()