#1942

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

The Number of the Smallest Unoccupied Chair

Solve The Number of the Smallest Unoccupied Chair by sorting arrivals and managing freed seats before each new assignment.

array hash table heap priority queue

Problem Statement

In The Number of the Smallest Unoccupied Chair, each friend arrives and leaves at known times, and every arrival must take the lowest-numbered chair that is free at that exact moment. Chairs are effectively unlimited, so the challenge is not capacity but assigning and reusing chair numbers in the correct order as events unfold.

The key detail is that a chair becomes reusable immediately when its owner leaves, including when another friend arrives at the same timestamp. Because arrival times are distinct, you can sort friends by arrival and process the timeline left to right, returning the chair assigned to targetFriend as soon as that friend is seated.

Examples

Example 1

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

Output: 1

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

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.length
2 <= n <= 104
times[i].length == 2
1 <= arrivali < leavingi <= 105
0 <= targetFriend <= n - 1
Each arrivali time is distinct.

Solution Approach

Sort arrivals and keep original friend indices

Start by transforming each entry into arrival, leaving, and friend index, then sort by arrival time. This lets you scan the party timeline once in the order chairs are assigned, while still knowing when you have reached targetFriend.

Track occupied chairs by earliest leaving time

Use a min-heap of occupied chairs storing leaving time and chair number. Before handling the next arrival, pop every occupied entry whose leaving time is less than or equal to the current arrival, because those chairs are already free and must be returned to the available pool before assigning a seat.

Always assign the smallest free chair

Use another min-heap for free chair numbers. If it is nonempty, pop its smallest chair; otherwise assign the next new chair number. When the current arriving friend is targetFriend, return that chair immediately. This avoids unnecessary simulation after the answer is known.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Sorting all friends costs O(n \log n), and each friend is pushed and popped from heaps at most once, so the full runtime stays O(n \log n). The heaps store up to O(n) chair and departure records, giving O(n) extra space.

What Interviewers Usually Probe

They point out that arrivals are distinct and suggest sorting by arrival time first.
They ask what should happen when someone leaves at the exact time another friend arrives.
They want the smallest available chair quickly, which is a strong hint for a min-heap instead of linear scanning.

Common Pitfalls or Variants

Common pitfalls

Freeing only one departed chair before seating the next friend instead of all chairs with leaving time less than or equal to the current arrival.
Using a hash table or array scan alone for chair selection, which misses the need to get the globally smallest free chair efficiently.
Losing the original friend index after sorting and returning the chair for the wrong person instead of targetFriend.

Follow-up variants

Return the full chair assignment array for every friend instead of only the target friend's chair.
Process online arrivals and departures where events are streamed rather than given as a full array upfront.
Replace smallest-chair assignment with another seating rule, such as largest free chair or nearest reusable chair.

FAQ

What is the main pattern in The Number of the Smallest Unoccupied Chair?

The core pattern is sorting arrivals, then combining timeline scanning with two min-heaps: one for occupied chairs by leaving time and one for reusable chair numbers. That structure enforces both immediate chair reuse and smallest-chair assignment.

Why is a plain array scan not enough for this problem?

A plain scan can find a free chair, but doing that for every arrival can degrade badly as n grows. This problem specifically needs the smallest free chair many times, so a min-heap gives that choice in logarithmic time.

Why do we free chairs before assigning the current arrival?

The statement says a chair becomes free at the exact leaving moment, so an arrival at that same time may use it immediately. If you assign first and release later, you can return a larger chair number than the correct answer.

Can I stop as soon as targetFriend is seated?

Yes. Once you process arrivals in sorted order and correctly release all eligible chairs first, the chair you assign to targetFriend is final, so you can return it immediately.

What data should the occupied heap store?

Store at least leaving time and chair number. The leaving time tells you when the chair becomes reusable, and the chair number is what you push back into the available-chair heap after that friend leaves.

terminal

Solution

Solution 1: Priority Queue (Min-Heap)

First, we create a tuple for each friend consisting of their arrival time, leaving time, and index, then sort these tuples by arrival time.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        n = len(times)
        for i in range(n):
            times[i].append(i)
        times.sort()
        idle = list(range(n))
        heapify(idle)
        busy = []
        for arrival, leaving, i in times:
            while busy and busy[0][0] <= arrival:
                heappush(idle, heappop(busy)[1])
            j = heappop(idle)
            if i == targetFriend:
                return j
            heappush(busy, (leaving, j))

Continue Practicing

#1912 design movie rental system #2099 find subsequence of length k with the largest sum #2342 max sum of a pair with equal sum of digits