1
class Solution {
2
 public:
3
  int smallestChair(vector<vector<int>> &times, int targetFriend) {
4
    int n = times.size();
5
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
6
        busy; // departure time as first , index as second
7
    priority_queue<int, vector<int>, greater<int>>
8
        free; // min heap of chair index that are unoccupied
9

10
    // store friend indexes so that they don't get lost after sorting
11
    for (int i = 0; i < n; ++i) {
12
      times[i].push_back(i);
13
    }
14
    // Sort according to arrival time
15
    sort(times.begin(), times.end());
16

17
    int new_chair = 0; // chairs alloted till now
18
    for (int i = 0; i < n; ++i) {
19
      int arrival = times[i][0]; // pop chairs before arrival
20
      int leave_time = times[i][1];
21
      int fr = times[i][2]; // friend index
22
      // free chairs accordingly
23
      while (!busy.empty() && busy.top().first <= arrival) {
24
        // cout << "Chair free " << busy.top().second << endl;
25
        free.push(busy.top().second);
26
        busy.pop();
27
      }
28
      // No free chair allot new chair
29
      if (free.empty()) {
30
        // cout << "Alloting new_chair " << new_chair << "to" << fr << endl;
31
        if (fr == targetFriend) return new_chair;
32
        busy.push({leave_time, new_chair});
33
        new_chair++;
34
      } else {
35
        int x = free.top();
36
        // cout << "giving chair " << x << "to" << fr << endl;
37
        free.pop();
38
        if (fr == targetFriend) return x;
39
        busy.push({leave_time, x});
40
      }
41
    }
42
    return -1;
43
  }
44
};