1942

1942. The Number of the Smallest Unoccupied Chair (Medium)

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

• For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

 

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

 

Constraints:

• n == times.length
• 2 <= n <= 104
• times[i].length == 2
• 1 <= arrivali < leavingi <= 105
• 0 <= targetFriend <= n - 1
• Each arrivali time is distinct.

Solution 1. Heap

// OJ: https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int smallestChair(vector<vector<int>>& A, int targetFriend) {
        set<int> avail; // indices of available seats
        for (int i = 0; i < A.size(); ++i) avail.insert(i);
        auto target = A[targetFriend][0];
        sort(begin(A), end(A));
        auto cmp = [&](int a, int b) { return A[a][1] > A[b][1]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp); // min heap of indices of friends in seats. Friend at heap top has the earliest leave time
        unordered_map<int, int> seat; // mapping from friend index to seat index
        for (int i = 0; i < A.size(); ++i) {
            auto &v = A[i];
            while (pq.size() && A[pq.top()][1] <= v[0]) { // given the current arrival time, pop all the friends that have left
                int s = seat[pq.top()];
                avail.insert(s); // free the corresponding seat
                seat.erase(i);
                pq.pop();
            }
            int s = *avail.begin(); // take the seat with the smallest index available
            if (v[0] == target) return s;
            avail.erase(s);
            seat[i] = s;
            pq.push(i);
        }
        return -1;
    }
};

Or shorter code

// OJ: https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int smallestChair(vector<vector<int>>& A, int targetFriend) {
        int target = A[targetFriend][0];
        sort(begin(A), end(A));
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> used; // leave time, seat
        priority_queue<int, vector<int>, greater<>> avail;
        for (int i = 0; i < A.size(); ++i) avail.push(i);
        for (int i = 0; i < A.size(); ++i) {
            auto &v = A[i];
            while (used.size() && used.top().first <= v[0]) {
                avail.push(used.top().second);
                used.pop();
            }
            int s = avail.top();
            avail.pop();
            if (v[0] == target) return s;
            used.emplace(v[1], s);
        }
        return -1;
    }
};