The Number of the Smallest Unoccupied Chair

Medium
963.

The Number of the Smallest Unoccupied Chair

The Number of the Smallest Unoccupied Chair is a medium coding problem on arrays, hash table and heap, asked in Amazon, Google and CRED interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} times
 * @param {number} targetFriend
 * @return {number}
 */
var smallestChair = function(times, targetFriend) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Number of the Smallest Unoccupied Chair — Solution

The Number of the Smallest Unoccupied Chair solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

The Number of the Smallest Unoccupied Chair is a medium coding problem on arrays, hash table and heap, asked in Amazon, Google and CRED interviews.

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.

Hints for The Number of the Smallest Unoccupied Chair

  1. Hint 1

    Process the friends in order of arrival, not in input order.

  2. Hint 2

    Before seating someone, free every chair whose occupant has already left — leaving <= arrival counts as left.

  3. Hint 3

    The chair taken is the smallest free number; n chairs always suffice for n friends.

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

Java

public static int smallestChair(int[][] times, int targetFriend) {
    int n = times.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> times[a][0] - times[b][0]);
    PriorityQueue<Integer> free = new PriorityQueue<>();
    for (int i = 0; i < n; i++) free.add(i);
    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    for (int who : order) {
        int arrive = times[who][0], leave = times[who][1];
        while (!busy.isEmpty() && busy.peek()[0] <= arrive) free.add(busy.poll()[1]);
        int chair = free.poll();
        if (who == targetFriend) return chair;
        busy.add(new int[] { leave, chair });
    }
    return -1;
}

C++

int smallestChair(vector<vector<int>>& times, int targetFriend) {
    int n = (int) times.size();
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return times[a][0] < times[b][0]; });
    priority_queue<int, vector<int>, greater<int>> freeChairs;
    for (int i = 0; i < n; i++) freeChairs.push(i);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> busy;
    for (int who : order) {
        int arrive = times[who][0], leave = times[who][1];
        while (!busy.empty() && busy.top().first <= arrive) {
            freeChairs.push(busy.top().second);
            busy.pop();
        }
        int chair = freeChairs.top();
        freeChairs.pop();
        if (who == targetFriend) return chair;
        busy.push({ 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets