1942. The Number of the Smallest Unoccupied Chair

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.

Approach 01:

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int nextAvailableChair = 0;
        priority_queue<int, vector<int>, greater<>> availableChairs;
        using ChairEvent = pair<int, int>;  // (leavingTime, chairNumber)
        priority_queue<ChairEvent, vector<ChairEvent>, greater<>> occupiedChairs;

        // Append friend indices to the times
        for (int i = 0; i < times.size(); ++i) {
            times[i].push_back(i);
        }

        // Sort times by arrival time
        sort(times.begin(), times.end());

        for (const vector<int>& time : times) {
            int arrivalTime = time[0];
            int leavingTime = time[1];
            int friendIndex = time[2];

            // Free up chairs for friends who have left by the current arrival time
            while (!occupiedChairs.empty() && occupiedChairs.top().first <= arrivalTime) {
                availableChairs.push(occupiedChairs.top().second);
                occupiedChairs.pop();
            }

            // If the current friend is the target friend
            if (friendIndex == targetFriend) {
                return availableChairs.empty() ? nextAvailableChair : availableChairs.top();
            }

            // Assign the next available chair
            if (availableChairs.empty()) {
                occupiedChairs.emplace(leavingTime, nextAvailableChair++);
            } else {
                occupiedChairs.emplace(leavingTime, availableChairs.top());
                availableChairs.pop();
            }
        }

        throw;  // This shouldn't be reached
    }
};

import heapq

class Solution:
    def smallestChair(self, times, targetFriend):
        nextAvailableChair = 0
        availableChairs = []
        occupiedChairs = []

        # Append friend indices to the times list
        for i in range(len(times)):
            times[i].append(i)

        # Sort times by arrival time
        times.sort()

        for arrivalTime, leavingTime, friendIndex in times:
            # Free up chairs for friends who have left by the current arrival time
            while occupiedChairs and occupiedChairs[0][0] <= arrivalTime:
                _, chairNumber = heapq.heappop(occupiedChairs)
                heapq.heappush(availableChairs, chairNumber)

            # If the current friend is the target friend
            if friendIndex == targetFriend:
                return availableChairs[0] if availableChairs else nextAvailableChair

            # Assign the next available chair
            if availableChairs:
                chairNumber = heapq.heappop(availableChairs)
            else:
                chairNumber = nextAvailableChair
                nextAvailableChair += 1

            heapq.heappush(occupiedChairs, (leavingTime, chairNumber))

        raise Exception("This shouldn't be reached")

Time Complexity

• Sorting the times array:

  The function sorts the input vector times based on the arrival time, which takes \(O(n \log n)\), where \(n\) is the number of friends (or size of the input array).

• Iterating through the events:

  The function iterates through the sorted events once, processing each friend’s arrival and departure. For each event, chair assignment and freeing are performed using priority queues, which have logarithmic time complexity for insertion and removal. Therefore, this step takes \(O(n \log n)\) as well.

• Overall Time Complexity:

  The overall time complexity is \(O(n \log n)\), where \(n\) is the number of friends (or size of the input array). The most costly operation is sorting the array and handling priority queue operations.

Space Complexity

• Auxiliary Space:

  The function uses two priority queues: one for available chairs and another for occupied chairs. Both queues can store at most \(n\) elements, where \(n\) is the number of friends. Therefore, the space complexity is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the number of friends (or the size of the input vector), due to the space used by the priority queues.