• Posts

Problem 1942 The Number of the Smallest Unoccupied Chair

Problem Statement

Link - Problem 1942

Question

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

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

        vector<int> order(n);
        for (int i = 0; i < n; ++i) order[i] = i;

        sort(order.begin(), order.end(), [&times](int a, int b) {
            return times[a][0] < times[b][0];
        });

        priority_queue<int, vector<int>, greater<int>> emptySeats;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> takenSeats;

        for (int i = 0; i < n; ++i) emptySeats.push(i);

        for (int i : order) {
            int arrival = times[i][0], leave = times[i][1];

            while (!takenSeats.empty() && takenSeats.top().first <= arrival) {
                emptySeats.push(takenSeats.top().second);
                takenSeats.pop();
            }

            int seat = emptySeats.top();
            emptySeats.pop();

            if (i == targetFriend) return seat;

            takenSeats.push({leave, seat});
        }

        return -1;
    }
};

Complexity Analysis

| Algorithm                  | Time Complexity | Space Complexity |
| -------------------------- | --------------- | ---------------- |
| Priority Queue and Sorting | O(n log n)      | O(n)             |

Explanation

Intial Thoughts

To approach this problem, we need to first understand the party scenario and how friends occupy chairs. Key points to consider are: the arrival and departure times of friends, how they occupy the smallest available chair number, and how the chair becomes available when a friend leaves. We should also think about how to keep track of occupied and empty chairs. Some potential strategies could include using data structures like queues or priority queues to manage chair allocation.

Intuitive Analysis

Intuitively, solving this problem involves thinking about the timeline of arrivals and departures. We need to analyze the given times array and target friend, focusing on how the party unfolds over time. Important insights include prioritizing friends based on their arrival times, efficiently managing chair allocation using a suitable data structure, and identifying the chair assigned to the target friend. Additionally, considering edge cases such as simultaneous arrivals or departures can help ensure our solution is comprehensive. By visualizing the problem as a sequence of events and using an organized approach to track chair occupancy, we can develop an effective solution.

1. Intuition

• The problem requires finding the chair number that a specific friend will sit on, given the arrival and leaving times of all friends.
• To solve this, we need to simulate the process of friends arriving and leaving, and keep track of the available chairs.
• We can use a priority queue to store the available chairs, and another priority queue to store the chairs that are currently occupied.
• The key insight is to sort the friends by their arrival times, and then iterate through the sorted list to simulate the process.
• By using priority queues, we can efficiently find the smallest available chair and the chair that will be vacated the earliest.
• This approach ensures that we can find the correct chair number for the target friend in an efficient manner.
• The time complexity of this solution is O(n log n) due to the sorting and priority queue operations.

2. Implementation

• We start by sorting the friends based on their arrival times using the sort function and a lambda function as the comparison function: sort(order.begin(), order.end(), [&times](int a, int b) { return times[a][0] < times[b][0]; });
• We use two priority queues: emptySeats to store the available chairs and takenSeats to store the occupied chairs, along with the time when they will be vacated: priority_queue<int, vector<int>, greater<int>> emptySeats; and priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> takenSeats;
• We iterate through the sorted list of friends, and for each friend, we check if there are any chairs that will be vacated before they arrive: while (!takenSeats.empty() && takenSeats.top().first <= arrival) { emptySeats.push(takenSeats.top().second); takenSeats.pop(); }
• We then find the smallest available chair and assign it to the current friend: int seat = emptySeats.top(); emptySeats.pop();
• If the current friend is the target friend, we return the assigned chair number: if (i == targetFriend) return seat;
• Finally, we add the occupied chair to the takenSeats priority queue along with the time when it will be vacated: takenSeats.push({leave, seat});
• The solution handles the edge cases where a friend arrives at the same time as another friend leaves, by using the priority queues to ensure that the smallest available chair is always assigned.

Complexity Analysis

Time Complexity:

• The algorithm starts by sorting the order array based on the arrival times in times, which has a time complexity of O(n log n) due to the use of the sort function.
• After sorting, it iterates through the order array, using priority_queue operations like push and pop, which have an average time complexity of O(log n). Since this is done n times, the total time complexity for these operations is O(n log n).
• Given that the sorting operation dominates the overall time complexity, the algorithm’s time complexity is classified as O(n log n), where n is the number of friends.

Space Complexity:

• The algorithm uses several data structures: order, emptySeats, and takenSeats. The space used by these data structures is proportional to the number of friends (n), as in the worst case, all friends could be stored in these data structures.
• The emptySeats and takenSeats priority queues store at most n seats and n pairs of leave time and seat number, respectively. Additionally, the order array stores n indices.
• Since the total space used is directly proportional to the input size (n), the space complexity is O(n).

Footnote

This question is rated as Medium difficulty.

Hints

Sort times by arrival time.

for each arrival_i find the smallest unoccupied chair and mark it as occupied until leaving_i.