The Number of the Smallest Unoccupied Chair - Problem

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity.

When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrival_i, leaving_i], indicating the arrival and leaving times of the i^th friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

Input & Output

Example 1 — Basic Party Scenario

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

› Output: 1

💡 Note: Friend 0 arrives at time 1, sits in chair 0. Friend 1 arrives at time 2, sits in chair 1 (smallest available). Friend 1 leaves at time 3, but we already found the answer.

Example 2 — Chair Reuse

$ Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0

› Output: 2

💡 Note: Friend 1 arrives at time 1, sits in chair 0. Friend 2 arrives at time 2, sits in chair 1. Friend 0 arrives at time 3, sits in chair 2.

Example 3 — Immediate Chair Reuse

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

› Output: 0

💡 Note: Friend 0: arrives at 1, sits in chair 0, leaves at 2. Friend 1: arrives at 2, sits in chair 0 (just freed), leaves at 3. Friend 2: arrives at 3, sits in chair 0 (just freed again).

Constraints

n == times.length
2 ≤ n ≤ 10⁴
1 ≤ arrival_i < leaving_i ≤ 10⁵
0 ≤ targetFriend ≤ n - 1
Each arrival_i is distinct

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is to process arrival events chronologically while efficiently tracking the smallest available chair. The optimal approach uses a min-heap for available chairs and a priority queue for departures. Time: O(n log n), Space: O(n).

Common Approaches

✓ Brute Force Simulation

⏱️ Time: O(n² log n) Space: O(n)

Create events for all arrivals and departures, sort by time, then for each arrival scan from chair 0 to find the first available chair.

Heap-Based Optimization

⏱️ Time: O(n log n) Space: O(n)

Process events in chronological order using a min-heap to efficiently find the smallest available chair and a priority queue to handle departures.

Brute Force Simulation — Algorithm Steps

Create events for arrivals and departures
Sort events by time
For each arrival, scan chairs 0,1,2... to find first available
Track chair assignments and availability

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Events

Create and sort all arrival/departure events by time

Linear Scan

For each arrival, scan chairs from 0 until finding unoccupied

Assign Chair

Assign the first available chair to the friend

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int time;
    int eventType; // 0 = arrive, 1 = leave
    int friendId;
} Event;

static Event events[2000];
static int occupied[1000];
static int friendChair[1000];

int compareEvents(const void* a, const void* b) {
    Event* ea = (Event*)a;
    Event* eb = (Event*)b;
    if (ea->time != eb->time) {
        return ea->time - eb->time;
    }
    // At same time: leave (1) comes before arrive (0)
    return eb->eventType - ea->eventType;
}

int solution(int times[][2], int n, int targetFriend) {
    int eventCount = 0;
    
    // Create arrival and departure events
    for (int i = 0; i < n; i++) {
        events[eventCount++] = (Event){times[i][0], 0, i}; // 0 = arrive
        events[eventCount++] = (Event){times[i][1], 1, i}; // 1 = leave
    }
    
    // Sort events by time, departures before arrivals at same time
    qsort(events, eventCount, sizeof(Event), compareEvents);
    
    memset(occupied, 0, sizeof(occupied));
    memset(friendChair, -1, sizeof(friendChair));
    
    for (int i = 0; i < eventCount; i++) {
        int time = events[i].time;
        int eventType = events[i].eventType;
        int friend = events[i].friendId;
        
        if (eventType == 0) { // arrive
            // Find smallest available chair
            int chair = 0;
            while (occupied[chair]) {
                chair++;
            }
            occupied[chair] = 1;
            friendChair[friend] = chair;
            
            if (friend == targetFriend) {
                return chair;
            }
        } else { // leave
            if (friendChair[friend] != -1) {
                occupied[friendChair[friend]] = 0;
            }
        }
    }
    
    return 0;
}

void parseArray(const char* str, int times[][2], int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == '[') {
            p++;
            times[*size][0] = (int)strtol(p, (char**)&p, 10);
            while (*p == ' ' || *p == ',') p++;
            times[*size][1] = (int)strtol(p, (char**)&p, 10);
            while (*p && *p != ']') p++;
            if (*p == ']') p++;
            (*size)++;
        } else if (*p == ']' || *p == '\0') {
            break;
        } else {
            p++;
        }
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse times array
    static int times[1000][2];
    int n = 0;
    parseArray(line, times, &n);
    
    fgets(line, sizeof(line), stdin);
    int targetFriend = atoi(line);
    
    int result = solution(times, n, targetFriend);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

O(n log n) to sort events, O(n) arrivals each scanning O(n) chairs

⚡ Linearithmic

Space Complexity

O(n)

Store events array and chair occupancy tracking

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

893 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

The Number of the Smallest Unoccupied Chair - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler