Skip to content

2102. Sequentially Ordinal Rank Tracker 👍

  • Time:
    • Constructor: $O(1)$
    • add(name: str, score: int): $O(|\texttt{add()}|)$
    • get(): $O(|\texttt{get()}|)$
  • Space: $O(|\texttt{add()}|)$
 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Location {
  string name;
  int score;
  Location(const string& name, int score)
      : name(std::move(name)), score(score) {}
};

class SORTracker {
 public:
  void add(const string& name, int score) {
    l.emplace(name, score);
    if (l.size() > k + 1) {
      const Location location = l.top();
      l.pop();
      r.emplace(location.name, location.score);
    }
  }

  string get() {
    const string name = l.top().name;
    if (!r.empty()) {
      const Location location = r.top();
      r.pop();
      l.emplace(location.name, location.score);
    }
    ++k;
    return name;
  }

 private:
  struct CompareLeftMinHeap {
    bool operator()(const Location& a, const Location& b) {
      return a.score == b.score ? a.name < b.name : a.score > b.score;
    }
  };

  struct CompareRightMaxHeap {
    bool operator()(const Location& a, const Location& b) {
      return a.score == b.score ? a.name > b.name : a.score < b.score;
    }
  };

  priority_queue<Location, vector<Location>, CompareLeftMinHeap> l;
  priority_queue<Location, vector<Location>, CompareRightMaxHeap> r;
  int k = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class SORTracker {
  public void add(String name, int score) {
    l.offer(new Location(name, score));
    if (l.size() > k + 1)
      r.offer(l.poll());
  }

  public String get() {
    final String name = l.peek().name;
    if (!r.isEmpty())
      l.offer(r.poll());
    ++k;
    return name;
  }

  private record Location(String name, int score) {}

  private Queue<Location> l = new PriorityQueue<>(
      (a, b) -> a.score == b.score ? -a.name.compareTo(b.name) : Integer.compare(a.score, b.score));
  private Queue<Location> r = new PriorityQueue<>(
      (a, b) -> a.score == b.score ? a.name.compareTo(b.name) : Integer.compare(b.score, a.score));
  private int k;
}

 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
class Location:
  def __init__(self, name: str, score: int):
    self.name = name
    self.score = score

  def __lt__(self, location):
    if self.score == location.score:
      return self.name > location.name
    return self.score < location.score


class SORTracker:
  def __init__(self):
    self.l = []
    self.r = []
    self.k = 0  the number of times get() called

  def add(self, name: str, score: int) -> None:
    heapq.heappush(self.l, Location(name, score))
    if len(self.l) > self.k + 1:
      location = heapq.heappop(self.l)
      heapq.heappush(self.r, (-location.score, location.name))

  def get(self) -> str:
    name = self.l[0].name
    if self.r:
      topScore, topName = heapq.heappop(self.r)
      heapq.heappush(self.l, Location(topName, -topScore))
    self.k += 1
    return name