the-number-of-the-smallest-unoccupied-chair.cpp

// Time:  O(nlogn)
// Space: O(n)

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        vector<tuple<int, bool, int>> events;
        for (int i = 0; i < size(times); ++i) {
            events.emplace_back(times[i][0], true, i);
            events.emplace_back(times[i][1], false, i);
        }
        sort(begin(events), end(events));

        unordered_map<int, int> lookup;
        priority_queue<int, vector<int>, greater<int>> min_heap;
        for (const auto& [_, arrival, i] : events) {
            if (!arrival) {
                min_heap.emplace(lookup[i]);
                lookup.erase(i);
                continue;
            }
            if (!empty(min_heap)) {
                lookup[i] = min_heap.top(); min_heap.pop();
            } else {
                lookup[i] = size(lookup);
            }
            if (i == targetFriend) {
                break;
            }
        }
        return lookup[targetFriend];
    }
};