The Number of the Smallest Unoccupied Chair

The Number of the Smallest Unoccupied Chair is LeetCode 1942. It asks you to simulate a party where friends arrive and leave at different times, and each friend sits in the lowest-numbered available chair. Given a target friend, you need to figure out which chair they end up in. The trick is doing this efficiently with two heaps instead of scanning chairs on every arrival.

The problem

There is a party with n friends numbered 0 to n - 1. An infinite number of chairs are numbered 0, 1, 2, .... When a friend arrives, they sit in the smallest unoccupied chair. When a friend leaves, their chair becomes available again.

You are given a 2D array times where times[i] = [arrival_i, leaving_i] describes when friend i arrives and leaves. You are also given an integer targetFriend. Return the chair number that targetFriend will sit in.

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1

Why simulation works

The problem is naturally sequential. Friends arrive one at a time (sorted by arrival), and each arrival depends on who has already left. You cannot determine a friend's chair without processing every earlier event first.

This makes event-driven simulation the right approach. You process arrivals in chronological order, and before each arrival, you check whether any previous friends have already left, freeing up their chairs.

The approach: two heaps

Sort the friends by arrival time. Then process each friend in order:

1. Free expired chairs. Before seating the current friend, check the occupied heap. Any entry whose leave_time is at or before the current arrival time means that friend has left. Pop those entries and push their chair numbers back onto the available heap.
2. Assign the smallest chair. Pop the minimum from the available heap. That is the chair this friend sits in.
3. Track the occupation. Push (leave_time, chair) onto the occupied heap so the chair can be freed later.
4. Check for the target. If this friend is the target, return the chair number immediately.

The available chairs heap starts with [0, 1, 2, ..., n-1]. You only need n chairs at most because there are only n friends.

Step-by-step walkthrough

A few things to notice:

• The available heap always gives you the smallest free chair in O(log n).
• The occupied heap lets you batch-free all chairs whose occupants left before the current arrival, also in O(log n) per operation.
• You can stop as soon as you seat the target friend. No need to simulate the rest.

The code

import heapq

def smallest_chair(times, target_friend):
    n = len(times)
    order = sorted(range(n), key=lambda i: times[i][0])
    available = list(range(n))
    heapq.heapify(available)
    occupied = []

    for i in order:
        arrival, leaving = times[i]

        while occupied and occupied[0][0] <= arrival:
            leave_time, chair = heapq.heappop(occupied)
            heapq.heappush(available, chair)

        chair = heapq.heappop(available)

        if i == target_friend:
            return chair

        heapq.heappush(occupied, (leaving, chair))

    return -1

1. Sort by arrival. Create an index array sorted by each friend's arrival time. This preserves the original indices so you can identify the target friend.
2. Initialize the available heap. Chairs 0 through n-1 go into a min-heap. Popping always gives the smallest.
3. Free chairs before seating. For each arrival, pop all entries from the occupied heap where leave_time is at or before the current arrival. Push those chairs back into available.
4. Assign and check. Pop the smallest available chair. If this friend is the target, return immediately. Otherwise, push (leaving, chair) onto the occupied heap.

Complexity analysis

The brute force approach scans all chairs on every arrival to find the smallest free one, giving O(n) per friend and O(n^2) overall. The two-heap approach reduces each chair assignment and each chair release to O(log n), and since there are at most n arrivals and n departures, the total is O(n log n). The O(n log n) sort dominates.

Space is O(n) for both heaps and the sorted index array.

Building blocks

1. Event-driven simulation with heaps

Many scheduling problems follow the same pattern: sort events by time, then process them in order while maintaining a heap to track active resources. The occupied heap acts as a priority queue of "future events" (departures), and you drain it as time advances.

# General pattern: process events, free expired resources
while heap and heap[0][0] <= current_time:
    _, resource = heapq.heappop(heap)
    free(resource)

This same structure appears in Meeting Rooms II, where you track room end times, and in any problem where resources are allocated and released over time.

2. Min-heap for resource allocation

When you need to always pick the "smallest available" resource, a min-heap is the natural choice. It gives you O(log n) insertion and O(log n) extraction of the minimum. The alternative, scanning a list or set, costs O(n) per lookup.

# Always grab the smallest available resource
resource = heapq.heappop(available)
# ... use it ...
# Return it later
heapq.heappush(available, resource)

This pattern generalizes to any problem where you recycle numbered resources and always want the lowest-numbered one.

Edge cases

• Target is the first to arrive. They always get chair 0 since every chair is free.
• All friends arrive at different times with no overlap. Every friend sits in chair 0 because each previous friend leaves before the next arrives.
• All friends arrive at the same time. They are assigned chairs 0 through n-1 in order of their original indices (though the problem guarantees all arrival times are distinct).
• Target arrives last. You must simulate every prior arrival and departure before reaching the target.
• Large n (up to 10^4). The O(n log n) solution handles this comfortably within time limits.

From understanding to recall

This problem combines two building blocks that show up separately in many other problems: event-driven simulation and min-heap resource allocation. Understanding the approach is the easy part. The tricky part is remembering, under pressure, to use two separate heaps and to free chairs before assigning them.

Spaced repetition turns that understanding into recall. You write the solution from scratch, focusing on the mechanics: sort by arrival, drain the occupied heap, pop from available, check target. After a few reps at increasing intervals, the two-heap simulation pattern becomes automatic.

CodeBricks breaks this problem into its component building blocks and drills them independently. You practice the "free expired resources" loop on its own schedule, and the "min-heap allocation" pattern on its own. When a new problem combines both, you recognize the pieces instantly.

Related posts

• Meeting Rooms II - another interval scheduling problem using heaps
• Top K Frequent Elements - heap-based selection pattern
• Task Scheduler - another simulation problem with scheduling constraints

---

Understanding heap simulation patterns is one thing. Being able to write them from memory during an interview is another. CodeBricks uses spaced repetition to close that gap, drilling each building block until it sticks.