The Number of the Smallest Unoccupied Chair

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

Understanding the Visualization

Input

Times array with [arrival, departure] and target friend

Process

Assign chairs in chronological order, always using smallest available

Output

Chair number that target friend sits on

Key Takeaway

🎯 Key Insight: Process events chronologically and always assign the numerically smallest available chair

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

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n² log n)	O(n)	Simulate each arrival/departure event and scan for smallest available chair
Heap-Based Optimization	O(n log n)	O(n)	Use min-heap for available chairs and priority queue for 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;

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;
    }
    return ea->eventType - eb->eventType;
}

int solution(int times[][2], int n, int targetFriend) {
    Event events[2 * n];
    int eventCount = 0;
    
    // Create arrival and departure events
    for (int i = 0; i < n; i++) {
        events[eventCount++] = (Event){times[i][0], 0, i};
        events[eventCount++] = (Event){times[i][1], 1, i};
    }
    
    qsort(events, eventCount, sizeof(Event), compareEvents);
    
    int occupied[1000] = {0}; // Assume max 1000 chairs needed
    int friendChair[1000];
    memset(friendChair, -1, sizeof(friendChair));
    
    for (int i = 0; i < eventCount; i++) {
        Event event = events[i];
        
        if (event.eventType == 0) { // arrive
            // Find smallest available chair
            int chair = 0;
            while (occupied[chair]) {
                chair++;
            }
            occupied[chair] = 1;
            friendChair[event.friendId] = chair;
            
            if (event.friendId == targetFriend) {
                return chair;
            }
        } else { // leave
            if (friendChair[event.friendId] != -1) {
                occupied[friendChair[event.friendId]] = 0;
            }
        }
    }
    
    return 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse times array manually
    int times[1000][2];
    int n = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            times[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            times[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            n++;
        } else {
            ptr++;
        }
    }
    
    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

⚠ Quadratic Growth

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler