Get started

The Number of the Smallest Unoccupied Chair — Medium Problem & Solution

A party has infinitely many chairs numbered 0, 1, 2, …. times[i] = [arrival, leaving] gives when friend i arrives and leaves; all the arrival times are…

Problem statement

A party has infinitely many chairs numbered 0, 1, 2, …. times[i] = [arrival, leaving] gives when friend i arrives and leaves; all the arrival times are different.

On arrival a friend takes the smallest-numbered unoccupied chair. A chair freed at moment t may be taken by someone arriving at that same moment t. Return the chair number that friend targetFriend sits on.

Example 1

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: Friend 0 takes chair 0, friend 1 takes chair 1.

Example 2

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: Friends 1 and 2 arrive first and take chairs 0 and 1.

Example 3

Input: times = [[1,2],[2,3]], targetFriend = 1
Output: 0
Explanation: Chair 0 is freed exactly as the second friend arrives.

Constraints

  • n == times.length
  • 2 <= n <= 10^4
  • times[i].length == 2
  • 1 <= arrival < leaving <= 10^5
  • 0 <= targetFriend <= n - 1
  • Each arrival time is distinct.

How to solve The Number of the Smallest Unoccupied Chair

Simulate the party in arrival order. Before each arrival, release the chairs whose occupants have gone, then hand out the smallest free chair number.

Approach

  1. Sort the friend indices by arrival time.
  2. For each arrival, mark free any chair whose recorded leaving time is at most this arrival.
  3. Take the lowest-numbered free chair; if the arriving friend is the target, that is the answer.
  4. Otherwise record the chair as occupied until that friend's leaving time.

Why it works

Only n chairs are ever needed, because at most n friends are present at once — which is what lets the free chairs live in a fixed-size array. The boundary is the subtle part: a chair freed at exactly the arrival moment is available, so the release test is <= rather than <. Two heaps — free chair numbers and occupied-by-leaving-time — turn the scan into O(n log n).

Complexity

  • Time — O(n²) as written, or O(n log n) with two heaps
  • Space — O(n)

Pitfalls

  • Processing the friends in input order instead of arrival order.
  • Using < to release chairs loses the same-moment handover.
  • Chairs are reused, so the answer is not simply the friend's rank in arrival order.

Reference solution

Python

from typing import List
import heapq

def smallestChair(times: List[List[int]], targetFriend: int) -> int:
    n = len(times)
    order = sorted(range(n), key=lambda i: times[i][0])
    free = list(range(n))
    heapq.heapify(free)
    busy = []
    for who in order:
        arrive, leave = times[who]
        while busy and busy[0][0] <= arrive:
            _, chair = heapq.heappop(busy)
            heapq.heappush(free, chair)
        chair = heapq.heappop(free)
        if who == targetFriend:
            return chair
        heapq.heappush(busy, (leave, chair))
    return -1

JavaScript

var smallestChair = function(times, targetFriend) {
    var n = times.length, i;
    var order = [];
    for (i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return times[a][0] - times[b][0]; });
    var freeAt = [], inUse = [];
    for (i = 0; i < n; i++) { freeAt.push(0); inUse.push(false); }
    for (var k = 0; k < order.length; k++) {
        var who = order[k];
        var arrive = times[who][0];
        for (var c = 0; c < n; c++) {
            if (inUse[c] && freeAt[c] <= arrive) inUse[c] = false;
        }
        var chair = 0;
        while (inUse[chair]) chair++;
        if (who === targetFriend) return chair;
        inUse[chair] = true;
        freeAt[chair] = times[who][1];
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue