Watch 10 video solutions for The Number of the Smallest Unoccupied Chair, a medium level problem involving Array, Hash Table, Heap (Priority Queue). This walkthrough by NeetCodeIO has 12,749 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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 |