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.Problem Overview: Friends arrive and leave at different times, and each one takes the smallest numbered unoccupied chair when they arrive. When a friend leaves, their chair becomes available again. Given the arrival/leave schedule and a target friend index, you need to determine which chair that friend sits on.
Approach 1: Min-Heap Simulation (O(n log n) time, O(n) space)
This approach models the process exactly as it happens using two heap (priority queue) structures. First, sort all friends by arrival time so events happen in chronological order. Maintain one min-heap for currently occupied chairs keyed by leaving time, and another min-heap that stores available chair numbers. When a friend arrives, repeatedly pop from the occupied heap if their leave time is less than or equal to the current arrival time, pushing those chair numbers back into the free heap. The arriving friend takes the smallest available chair from the free heap. If the arriving friend is the target friend, return that chair number immediately.
The key insight: you never need to simulate all chairs explicitly. The free heap always provides the smallest available chair in O(log n), while the occupied heap quickly releases chairs when friends leave. This solution fits naturally with array processing and event simulation.
Approach 2: Event Scheduling with Ordered Sets (O(n log n) time, O(n) space)
This approach treats arrivals and departures as ordered events and uses a balanced set structure to manage available chairs. Sort friends by arrival time. Maintain a set containing all currently free chair numbers and a structure mapping leave times to the chair occupied by that friend. As you iterate through arrivals, release chairs for all friends whose leave time has passed and reinsert those chair numbers into the set. The arriving friend always picks the smallest element from the set.
The ordered set guarantees that retrieving the smallest free chair takes O(log n). Tracking departures ensures chairs are recycled efficiently. This method often appears in C++ or Java implementations where ordered sets or tree structures are convenient. The scheduling idea closely resembles problems involving hash table lookups combined with sorted events.
Recommended for interviews: The min-heap simulation is the expected solution. It demonstrates understanding of event ordering, priority queues, and resource allocation problems. Explaining the simulation clearly shows strong problem modeling skills, while the heap operations keep the runtime optimal at O(n log n).
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.
Python
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.
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.
First, we create a tuple for each friend consisting of their arrival time, leaving time, and index, then sort these tuples by arrival time.
We use a min-heap idle to store the currently available chair numbers. Initially, we add 0, 1, ldots, n-1 to idle. We also use a min-heap busy to store tuples (leaving, chair), where leaving represents the leaving time and chair represents the chair number.
We iterate through each friend's arrival time, leaving time, and index. For each friend, we first remove all friends from busy whose leaving time is less than or equal to the current friend's arrival time, and add their chair numbers back to idle. Then we pop a chair number from idle, assign it to the current friend, and add (leaving, chair) to busy. If the current friend's index is equal to targetFriend, we return the assigned chair number.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of friends.
Python
Java
C++
Go
TypeScript
JavaScript
| 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. |
| Priority Queue (Min-Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap Simulation | O(n log n) | O(n) | General case; ideal when modeling arrivals and departures with priority queues |
| Event Scheduling with Ordered Sets | O(n log n) | O(n) | Useful when language libraries provide efficient ordered sets or trees |
The Number of the Smallest Unoccupied Chair - Leetcode 1942 - Python • NeetCodeIO • 12,749 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