Leetcode 1942: The Number of the Smallest Unoccupied Chair
In a party, there are n friends with distinct arrival and departure times. Each friend chooses the smallest available chair. The task is to determine the chair number where the friend numbered targetFriend will sit.
Problem
Approach
Steps
Complexity
Input: A 2D array times where times[i] = [arrivali, leavingi] indicates the arrival and leaving times of the ith friend, and an integer targetFriend representing the index of the target friend.
Example: times = [[1,5],[2,6],[3,8]], targetFriend = 1
Constraints:
• 2 <= n <= 10^4
• 1 <= arrivali < leavingi <= 10^5
• Each arrival time is distinct
• 0 <= targetFriend < n
Output: Return the chair number that the target friend will sit on.
Example: Output: 1
Constraints:
• The output is an integer representing the chair number.
Goal: The goal is to determine the chair number occupied by the target friend.
Steps:
• Sort the friends based on their arrival times.
• Use two priority queues: one for keeping track of the available chairs and another for tracking the chairs occupied by friends based on their leaving times.
• Assign the smallest available chair to each arriving friend and release the chair when a friend leaves.
• Check when the target friend arrives and assign their chair number.
Goal: The array contains the arrival and departure times for each friend. The times are within the given range, and the number of friends is manageable within the problem's constraints.
Steps:
• 2 <= n <= 10^4
• 1 <= arrivali < leavingi <= 10^5
• Each arrival time is distinct
• 0 <= targetFriend < n
Assumptions:
• The arrival and departure times for each friend are unique and provided in a correct format.
• Input: Example 1: times = [[1, 5], [2, 6], [3, 8]], targetFriend = 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 2 arrives at time 3 and sits on chair 2. At time 5, Friend 0 leaves and Friend 1 sits back in chair 0. Friend 2 stays until time 8. Since Friend 1 sits on chair 1, the answer is 1.
• Input: Example 2: times = [[1, 3], [2, 5], [3, 7], [4, 6]], targetFriend = 2
• Explanation: Friend 0 arrives at time 1 and sits on chair 0. Friend 1 arrives at time 2 and sits on chair 1. Friend 2 arrives at time 3 and sits on chair 2. Friend 1 leaves at time 5, Friend 2 leaves at time 7, and Friend 3 arrives at time 4. The target friend 2 sits on chair 2.
Approach: To determine the chair number for the target friend, we will manage chair availability using priority queues and ensure the correct allocation of chairs as friends arrive and leave.
Observations:
• We need to efficiently track both the arrival and departure times of friends.
• Using priority queues allows us to quickly find the smallest available chair and to manage which chairs are being occupied or released.
Steps:
• Sort the times by arrival time.
• Initialize two priority queues: one for available chairs and one for the occupied chairs based on leaving times.
• For each friend, check if any chair has been freed (based on departure times). If so, add it to the available chairs queue.
• Assign the smallest available chair to the arriving friend, and store their leaving time.
• Once the target friend arrives, return the chair number they occupy.
Empty Inputs:
• The problem ensures that there are no empty inputs.
Large Inputs:
• Handle scenarios with the maximum number of friends and their respective times efficiently.
Special Values:
• When only two friends are involved, the solution should still correctly track the chairs.
Constraints:
• Ensure that all times are within the provided limits and that the chair assignment is accurate.
int smallestChair(vector<vector<int>>& a, int t) {
int tt = a[t][0];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> reserve;
priority_queue<int, vector<int>, greater<int>> avail;
sort(a.begin(), a.end());
for(auto &t : a) {
while(!reserve.empty() && reserve.top().first <= t[0]) {
avail.push(reserve.top().second);
reserve.pop();
}
if(t[0] == tt) break;
if (!avail.empty()) {
reserve.push({t[1], avail.top()});
avail.pop();
} else {
reserve.push({t[1], reserve.size()});
}
}
return avail.empty()? reserve.size() : avail.top();
}
1 : Function Declaration
int smallestChair(vector<vector<int>>& a, int t) {
Declare the function `smallestChair`, which accepts a 2D vector `a` representing event start and end times, and an integer `t` indicating the target time.
2 : Time Extraction
int tt = a[t][0];
Extract the start time `tt` of the event at index `t`.
3 : Priority Queue Initialization (Reservation)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> reserve;
Initialize a priority queue `reserve` to store pairs of end times and chair indices, sorted by the end time.
4 : Priority Queue Initialization (Available Chairs)
priority_queue<int, vector<int>, greater<int>> avail;
Initialize a priority queue `avail` to manage the available chair indices, sorted in ascending order.
5 : Sorting Events
sort(a.begin(), a.end());
Sort the events in `a` by their start times.
6 : Event Iteration
for(auto &t : a) {
Loop through each event `t` in the sorted list of events.
7 : While Loop (Check Expired Reservations)
while(!reserve.empty() && reserve.top().first <= t[0]) {
Check if there are any expired reservations (those whose end time is less than or equal to the current event's start time).
8 : Push to Available Chairs
avail.push(reserve.top().second);
Push the chair index from the top reservation (expired) into the `avail` queue to make it available.
9 : Pop Expired Reservation
reserve.pop();
Pop the top reservation from the `reserve` queue as it is now expired.
10 : Check Target Time
if(t[0] == tt) break;
If the current event's start time is equal to the target time `tt`, break the loop.
11 : Check Available Chairs
if (!avail.empty()) {
If there are available chairs, proceed to assign one.
12 : Push to Reserve (Available Chair)
reserve.push({t[1], avail.top()});
Assign an available chair (from the `avail` queue) to the current event and add the reservation to the `reserve` queue.
13 : Else (No Available Chair)
} else {
If there are no available chairs, assign a new one.
14 : Push to Reserve (New Chair)
reserve.push({t[1], reserve.size()});
Assign a new chair index (based on the size of `reserve` queue) to the current event and add the reservation to the `reserve` queue.
15 : Return Statement
return avail.empty()? reserve.size() : avail.top();
Return the index of the smallest available chair, or the total number of reservations if no chairs are available.
Best Case: O(n log n), due to sorting the arrival times and managing the queues.
Average Case: O(n log n), for each friend's arrival and departure time management.
Worst Case: O(n log n), as each friend's event needs to be processed and sorted.
Description: The time complexity is dominated by the sorting of the arrival times and the operations on the priority queues.
Best Case: O(n), as we may need to track up to n chairs at once.
Worst Case: O(n), for storing the event times and the state of each chair.
Description: The space complexity is linear with respect to the number of friends, as we need to track their arrival and departure times along with the chairs.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus