Description

Submission

class Solution {
    typedef pair<int, int> PII;
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size();

        for(int i = 0; i < n; ++i) {
            times[i].push_back(i);
        }
        sort(times.begin(), times.end());

        priority_queue<int, vector<int>, greater<>> chairs;
        priority_queue<PII, vector<PII>, greater<>> seated; // time to leave, chair index

        for(int i = 0; i < n; ++i) {
            chairs.push(i);
        }

        for(int i = 0; i < n; ++i) {
            int arrival = times[i][0];
            int leaving = times[i][1];

            while(!seated.empty() && seated.top().first <= arrival) {
                auto [ttl, idx] = seated.top();
                seated.pop();
                chairs.push(idx);
            }

            if(times[i][2] == targetFriend) {
                return chairs.top();
            }

            seated.push({leaving, chairs.top()});
            chairs.pop();
        }

        return -1;
    }
};