LeetCode 1942. The Number of the Smallest Unoccupied Chair

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    using PII = pair<int, int>;
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size(), tt = times[targetFriend][0];
        sort(times.begin(), times.end());
        priority_queue<int, vector<int>, greater<int>> q1; // available
        priority_queue<PII, vector<PII>, greater<PII>> q2; // unavailable
        for (int i = 0; i < n; ++i) q1.emplace(i);
        for (int i = 0; i < n; ++i) {
            while (!q2.empty() && q2.top().first <= times[i][0]) {
                q1.emplace(q2.top().second);
                q2.pop();
            }
            if (times[i][0] == tt) return q1.top();
            q2.emplace(times[i][1], q1.top());
            q1.pop();
        }
        return 0;
    }
};