1942. The Number of the Smallest Unoccupied Chair - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

There is a party with n friends numbered from 0 to n-1. The party has an infinite number of chairs labeled 0, 1, 2, ... and so on. Each friend has an arrival time and a leaving time. When a friend arrives, they will sit in the smallest-numbered chair that is not occupied at that moment. When a friend leaves, their chair becomes free for others to use. If a friend arrives exactly when another friend leaves, the arriving friend can immediately take the chair that just became free.

You are given a 0-indexed 2D array times where times[i] = [arrival_i, leaving_i] for friend i. (All arrival times are distinct.) You are also given an integer targetFriend – the index of one particular friend. Your task is to return the chair number that friend 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 takes chair 0 (the smallest available chair).
- Friend 1 arrives at time 2 and takes the next smallest available chair, which is chair 1.
- Friend 1 leaves at time 3, so chair 1 becomes free.
- Friend 0 leaves at time 4, so chair 0 becomes free.
- Friend 2 arrives at time 4 and takes the smallest available chair (which is chair 0, now free).
- Friend 1 sat on chair 1, so the answer is 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 finds chairs 0 and 1 occupied, so he takes chair 2 (the smallest free chair).
- Friend 1 leaves at time 5, freeing chair 0.
- Friend 2 leaves at time 6, freeing chair 1.
- Friend 0 leaves at time 10, freeing chair 2.
- Friend 0 sat on chair 2, so the answer is 2.

Key Details:

If chairs 0, 1, and 5 are occupied when a friend arrives, that friend will sit on chair 2 (since it’s the smallest unoccupied number at that time).
When a friend leaves at a certain time, their chair becomes immediately available at that same time for any other friend arriving at that moment.

Constraints:

n == times.length
2 <= n <= 10^4
Each times[i] has length 2 (an arrival and a leaving time).
1 <= arrival_i < leaving_i <= 10^5
0 <= targetFriend < n
All arrival times are distinct.

Hints

Think in chronological order: Consider simulating the party timeline. Sort the friends by their arrival times so you can process the events (arrivals and departures) in the order they happen.
Manage chair availability: When a friend leaves, their chair becomes free. When the next friend arrives, they should get the smallest free chair. How can you efficiently find the smallest free chair? (Hint: a min-heap or another ordered data structure can help pick the smallest available chair quickly.)
Two groups of chairs: Try using one min-heap to keep track of free chairs (by their chair numbers), and another to keep track of occupied chairs along with their leave times. As time progresses, move chairs from the occupied heap back to the free heap when they become free (when a friend leaves). This way, at any arrival, the smallest free chair is ready to be assigned.

Approach 1: Brute Force Simulation

Explanation:
A straightforward way to solve this problem is to simulate each event (friend arrival or departure) in order. We can maintain a list or array of chair statuses (which chairs are free or occupied) and update it as friends come and go. For each arriving friend, we scan from chair 0 upwards to find the first free chair and assign it to them. We also keep track of when each friend leaves to free up their chair at the correct time.

Steps for Brute Force:

Sort events by time: Create a list of all events (arrivals and departures). Each event can be represented as (time, type, friendIndex), where type is arrival or departure. Sort this list by time. If an arrival and departure happen at the same time, process the departure first (so the chair is free for the arrival).
Track chair occupancy: Maintain a boolean array occupied to indicate if a chair is currently taken. Since there are at most n friends, you will never need more than n chairs (indexed 0 through n-1) at any one time. Initialize all chairs as free (False in occupied array).
Simulate the timeline: Iterate through the sorted events:
- If a friend leaves, mark their chair as free in occupied. (You may need to know which chair they were using; you can store that when they arrived.)
- If a friend arrives, scan the occupied array from index 0 upward to find the first False (free chair). Assign that chair to the arriving friend (mark it True as occupied and record which chair the friend got).
- If the arriving friend is the targetFriend, you can record or return that chair number as the answer.
Result: Return the chair number assigned to targetFriend during the simulation.

This brute force approach is easy to understand but may be inefficient because for each arriving friend (up to n friends), scanning the chairs (up to n chairs) takes O(n) time, resulting in O(n^2) in the worst case.

Brute Force Example (for understanding):
Using Example 1 (times = [[1,4],[2,3],[4,6]]):

At time 1, friend 0 arrives. Chairs [0,1,2] are all free, the smallest free is 0, so friend 0 sits in chair 0.
At time 2, friend 1 arrives. Chair 0 is occupied (by friend 0), chairs 1 and 2 are free, so the smallest free is 1. Friend 1 sits in chair 1.
At time 3, friend 1 leaves, freeing chair 1. (Now chairs 1 and 2 are free, chair 0 is still occupied by friend 0.)
At time 4, friend 0 leaves (freeing chair 0) and friend 2 arrives simultaneously. We process the leave first: now chairs 0,1,2 are all free. Friend 2 arrives and takes chair 0 (the smallest free).
At time 6, friend 2 leaves, freeing chair 0 (all chairs free again).
We note that targetFriend = 1 sat on chair 1.

Brute Force Implementation (Python): Below is a simple simulation following the above logic. We use 0 to denote a departure event (so it gets processed before an arrival at the same time, denoted by 1). We scan for the first free chair on each arrival.

Python3

. . . .

Brute Force Complexity:

Time Complexity: $O(n^2)$ in the worst case. In the worst scenario (e.g., if each new friend arrives before any previous friend leaves), each arrival might scan through almost n chairs to find a free one. With n friends, that results in about n * n checks. For $n = 10^4$ , this could be on the order of $10^8$ operations, which is likely too slow in practice.
Space Complexity: O(n) for storing chair occupancy and mappings. We use additional space for event storage (O(2n) which is O(n)).

Note: The brute-force approach works logically but will become slow for large inputs (near the upper constraints). We use it here for clarity and correctness, but we'll need to optimize to handle n=10^4 efficiently.

Approach 2: Optimized Approach (Using Min-Heaps)

Explanation:
To efficiently simulate the process, we can take advantage of priority queues (min-heaps) to always retrieve the smallest available chair quickly, and to manage chairs that will get freed. The idea is to process friend arrivals in increasing order of time, just like in the brute force solution, but use heaps to avoid scanning linearly for the free chair each time.

Key Data Structures:

Min-heap for free chairs: Keep a min-heap of all currently free chair numbers. This allows us to get the smallest free chair in O(log n) time. Initially, chairs 0 through n-1 can be considered available (at most n chairs will ever be needed).
Min-heap for occupied chairs (by leave time): Keep another min-heap of (leaving_time, chair_number) for chairs that are currently occupied. This heap is ordered by leaving time. When the current time advances to the next arrival, we can quickly free all chairs from this heap whose leaving time is <= current arrival time (meaning those friends have left by or at that time). We pop from this heap and add those chair numbers back into the free chairs heap.

Optimized Algorithm:

Sort friends by arrival time: Create a list of friends (indices 0..n-1) and sort it by their arrival times. This gives the order in which we will process arrivals.
Initialize heaps:
- freeChairs min-heap containing chair numbers 0, 1, ..., n-1 (all chairs initially free).
- occupied min-heap for occupied chairs, initially empty.
Process each friend in arrival order: For each friend in sorted-by-arrival sequence:
- Let curr_time be this friend's arrival time. First, free up chairs for all friends who have left on or before curr_time: while the occupied heap is not empty and its smallest leaving time <= curr_time, pop from occupied and push that chair number back into freeChairs (marking those chairs as free).
- Now, assign the arriving friend to the smallest available chair: pop the top chair number from freeChairs. This is the smallest free chair at that time. Record this assignment.
- Push this chair into the occupied heap along with the friend's leaving time, so it becomes occupied until that time.
- If this friend is the targetFriend, record the chair number as the answer (and you could even return it immediately since we found what we need).
Result: Return the recorded chair number for targetFriend.

Using heaps ensures that both freeing chairs and assigning a new chair are efficient operations (logarithmic time). We never scan all chairs explicitly; we only push and pop from heaps.

Why it works: By processing events in sorted order, we ensure that by the time we handle an arrival, we have already freed all chairs from friends who left earlier. The freeChairs heap always contains exactly those chairs that are currently free, and we always take the smallest one. This matches the problem's rule. The occupied heap helps manage future chair free-up events.

Walkthrough of Optimized Approach (Step-by-Step):
Let's walk through Example 1 using this approach, showing the state of the heaps at each step:

Time	Event	Free Chairs (min-heap)	Occupied (min-heap of [leaveTime, chair])	Chair Assigned
1	Friend 0 arrives	Free: {0,1,2} (initially all free)	Occupied: {} (empty)	Friend 0 takes chair 0
	(Assign chair 0 to Friend 0)	Free now: {1,2}	Occupied: {(4, 0)} (chair 0 busy until t=4)
2	Friend 1 arrives	Free: {1,2}	Occupied: {(4, 0)}	Friend 1 takes chair 1
	(Assign chair 1 to Friend 1)	Free now: {2}	Occupied: {(3, 1), (4, 0)} (chair 1 busy until t=3, chair 0 until t=4)
3	Friend 1 leaves (time 3)	Free: {2}	Occupied: {(3, 1), (4, 0)}	(Chair 1 becomes free)
	Free chair 1 from occupied heap	Free now: {1,2}	Occupied: {(4, 0)}	(Friend 1's chair freed)
4	Friend 0 leaves (time 4)	Free: {1,2}	Occupied: {(4, 0)}	(Chair 0 becomes free)
	Free chair 0 from occupied heap	Free now: {0,1,2}	Occupied: {}	(Friend 0's chair freed)
4	Friend 2 arrives (time 4)	Free: {0,1,2}	Occupied: {}	Friend 2 takes chair 0 (smallest free)
	(Assign chair 0 to Friend 2)	Free now: {1,2}	Occupied: {(6, 0)} (chair 0 busy until t=6)
6	Friend 2 leaves (time 6)	Free: {1,2}	Occupied: {(6, 0)}	(Chair 0 becomes free)
	Free chair 0 from occupied heap	Free now: {0,1,2}	Occupied: {}	(Friend 2's chair freed)

In the above table:

Free Chairs shows the content of the free chairs min-heap at the moment before the event (with the smallest free chair in bold or at the front).
Occupied shows the content of the occupied heap as a set of pairs (leavingTime, chair).
Chair Assigned indicates which chair an arriving friend takes.
We can see that Friend 1 (the target) was assigned chair 1 at time 2. The algorithm correctly tracked chair availability.

Optimized Implementation (Python): Using two heaps (heapq for min-heap in Python).

Python3

. . . .

Optimized Implementation (Java): Using PriorityQueue for two heaps.

Java

. . . .

Optimized Approach Complexity:

Time Complexity: O(n log n). Sorting the friends by arrival time takes O(n log n). Then, for each friend, we perform at most two heap operations (one removal from freeChairs and one insertion into occupied, plus some removals from occupied when freeing chairs). Each heap operation is O(log n), so the per-friend processing is O(log n) on average. Overall this gives roughly O(n log n) time. For n = 10^4, this is very efficient (on the order of $10^4 * log(10^4) \approx 10^4 * 14 \approx 1.4\times10^5$ operations).
Space Complexity: O(n) for the heaps and other structures. We store at most n chair indices in freeChairs and at most n entries in occupied. We also store sorted friend indices (O(n)). The space usage is linear in the number of friends.

Common Mistakes and Pitfalls

Not sorting events or friends by time: A common mistake is to try simulating in the given order of input. You must sort by arrival time to process events in the correct chronological order.
Handling simultaneous events incorrectly: If a friend leaves at the exact same time another arrives, you should free the chair before assigning it to the arriving friend. Forgetting this (or doing it in reverse) can lead to assigning a new chair when an old one should have been reused. Always process departures at a given time before arrivals at that same time.
Scanning linearly for chairs (inefficiently): While a brute force scan works on small cases, it will time out for large inputs. Relying on something like min() on a list of free chairs repeatedly, or checking from chair 0 upwards for each arrival without an efficient break, can be too slow. Using a min-heap or an ordered set is the intended solution for efficiency.
Using fixed-size structures incorrectly: Assuming you only need n-1 chairs or exactly n chairs and not handling the case where chair n-1 becomes occupied and a new friend arrives (they would take chair n, which is index n since counting from 0). In this problem, because there are n friends, the maximum chair index that could be used is n-1 (when all friends are present, chairs 0 through n-1 are occupied). But if one isn’t careful, an off-by-one error could occur in managing the chair numbers. Initializing the free chairs from 0 to n-1 covers all possible chairs needed.
Not tracking chairs per friend: You might forget to record which chair a friend took, which is necessary to free that specific chair later when the friend leaves. Always map a friend to their chair (or directly store the chair in the occupied heap with its leave time).

Edge Cases to Consider

Minimum input size: n = 2 (two friends). Ensure your solution works for a simple case of two friends with non-overlapping or overlapping times.
Target friend arrives first or last: If the target friend is the very first to arrive, they should always get chair 0. If the target friend is the last to arrive, make sure the algorithm correctly gives them the next available chair (which could be a higher-numbered chair if all others are taken).
Back-to-back timings: Cases where one friend leaves at the exact same time another arrives (or multiple leave at the same time someone arrives). For example, if friend A leaves at time 5 and friend B arrives at time 5, friend B should be able to take friend A’s chair. Our simulation must handle this by freeing chairs with leaving_time <= arrival_time (<=, not <).
Multiple friends leaving at the same time: If two or more friends leave at the same time T, and another friend arrives at time T, all chairs from those who left are free to use. The smallest of all freed chairs should be taken by the arriving friend. The algorithm should free all chairs up to and including the arrival time, not just one. (The while-loop in the optimized solution takes care of freeing multiple chairs that have leave_time <= arrival_time.)
Non-overlapping schedules: If friends come one after another and none overlap (each friend leaves before the next arrives), the target friend (or any friend) will always get chair 0 because it continuously becomes free and is reused. Ensure this scenario doesn’t break the logic (the code should still work, assigning 0 every time in sequence).
All friends overlapping: In the extreme case where every friend’s interval overlaps (at some point all are at the party together), the chairs will be allocated from 0 up to n-1. The target friend in such a case will get their appropriate chair in that range. The algorithm should handle this heavy overlap by still returning the correct chair index.

Alternative Variations of the Problem

This problem can be adapted or extended in a few ways:

Multiple Arrivals at the Same Time: In this variation, two or more friends could arrive exactly at the same time. The problem would need to specify how to break ties (e.g. by friend ID or just any could take the lowest chairs). The current approach could handle this by processing arrivals with the same timestamp sequentially (after freeing chairs from leavers at that time). You might sort such simultaneous arrivals by their friend IDs just to have a deterministic outcome when they grab chairs (smallest ID gets smallest chair, etc.).
Limited Number of Chairs: Another variation could impose a limit on the number of chairs (not infinite). If a friend arrives and all chairs are occupied, what happens? This would turn into a different problem (perhaps the friend has to wait or stand). Our solution assumes infinite chairs, but at most n are needed for n friends. If fewer than n chairs were available, you would need logic to handle waiting or queueing of friends until a chair frees up.
Returning a Different Result: Instead of asking for the chair number of a specific friend, a variation might ask for the maximum number of chairs ever occupied at once (peak chair usage, which is essentially the maximum number of overlapping intervals – similar to the “meeting rooms” problem). Or it might ask for the chair assignment for all friends. These would require slight modifications: for peak usage, you could count how many chairs become occupied at the busiest time; for all assignments, you would simulate fully and return the mapping of friend -> chair.
Continuous Timeline Simulation: A twist could be to simulate time units (if times were not too large) and check events at each time step. This is generally inefficient for large time ranges, but conceptually simpler. We avoided this in our solution in favor of event-driven simulation, which is more efficient.

Solving this problem involves understanding interval scheduling and the use of min-heaps for managing resources. Here are some related problems that you might find interesting:

Meeting Rooms II (LeetCode 253): Given meeting time intervals, find the minimum number of conference rooms required. This is similar in that you track ongoing meetings (equivalent to occupied chairs) and free a room when a meeting ends. A very similar heap approach (min-heap of end times) is used.
Seat Reservation Manager (LeetCode 1845): Design a system that manages seat reservations for a library (or similar). It always gives out the smallest-numbered free seat and can free a seat when a student leaves. This directly uses a min-heap to track available seat numbers, just like the chair allocation here.
Process Tasks Using Servers (LeetCode 1882): You have servers with certain capacities and tasks arriving over time. When multiple servers are free, the one with the smallest index gets the task. This problem uses a very similar strategy of two heaps: one for free servers (by index) and one for busy servers (by time when they become free). It's like an extended version of the chair problem with two ordering criteria (server weight and index).
Minimum Number of Platforms (Train Schedule problem): A classic problem where you are given arrival and departure times of trains and need to find the minimum number of platforms needed so that no train waits. It’s conceptually similar to Meeting Rooms II (greedy approach with sorting and counting overlaps).
Parking Lot or Bike Rental simulations: Problems that involve assigning the nearest or smallest-index resource to incoming requests and freeing them when done often use similar approaches with heaps or trees.

1942. The Number of the Smallest Unoccupied Chair - Detailed Explanation

Problem Statement

Hints

Approach 1: Brute Force Simulation

Approach 2: Optimized Approach (Using Min-Heaps)

Common Mistakes and Pitfalls

Edge Cases to Consider

Alternative Variations of the Problem

Related Problems for Further Practice