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.
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.length2 <= n <= 104times[i].length == 21 <= arrivali < leavingi <= 1050 <= targetFriend <= n - 1arrivali time is distinct.The problem can be efficiently solved by using a min-heap (priority queue) to keep track of the smallest available chair. When a friend arrives, we assign them the smallest chair, and when they leave, their chair is added back to the pool of available chairs. This ensures that friends always get the smallest possible available chair.
We start by sorting all events by time. As we process each event, we use the heap to efficiently manage the available chairs.
This Python function uses two main structures: a list of events that are sorted by time, and a min-heap to keep track of the smallest available chairs. We iterate through each event, either assigning an available chair to an arriving friend or freeing up a chair when a friend leaves. This method works because the heap operations are logarithmic, keeping the solution efficient.
JavaScript
Time Complexity: O(n log n), where n is the number of friends (and thus events). This is due to sorting the events and using heap operations.
Space Complexity: O(n) for storing event data and the heap.
This approach involves handling chair availability using a sorted list (or equivalent structure) to manage the sequence of chairs efficiently. We simulate arrival and departure events by updating the list and assigning chairs accordingly. While slightly less efficient than a heap in handling dynamic minimum queries, it offers an alternative perspective by focusing on set management operations.
This C++ solution uses a sorted set (implemented typically with Red-Black Trees in the STL set) to track available chairs and assigns them to arriving friends. When a friend arrives, we select the smallest available chair, either from the set or by incrementing. When a friend leaves, we return the chair to the set.
Java
Time Complexity: O(n log n) primarily due to sorting events and set operations.
Space Complexity: O(n) for storing chair assignments and event data.
| Approach | Complexity |
|---|---|
| Min-Heap Approach | Time Complexity: O(n log n), where n is the number of friends (and thus events). This is due to sorting the events and using heap operations. |
| Event Scheduling with Sets | Time Complexity: O(n log n) primarily due to sorting events and set operations. |
The Number of the Smallest Unoccupied Chair - Leetcode 1942 - Python • NeetCodeIO • 11,922 views views
Watch 9 more video solutions →Practice The Number of the Smallest Unoccupied Chair with our built-in code editor and test cases.
Practice on FleetCode