The Number of the Smallest Unoccupied Chair

Med

#1771Time: O(T_max + N log N). The main loop runs T_max times. The total work for priority queue operations over the entire simulation is O(N log N).Space: O(N + T_max), where N is the number of friends and T_max is the maximum leaving time. The maps for arrivals and departures can store up to T_max entries.1 company

Data structures

Array Hash Table Heap (Priority Queue)

Companies

Otter.ai

Prompt

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.

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- 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
Explanation: 
- 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 <= 10⁴
times[i].length == 2
1 <= arrival_i < leaving_i <= 10⁵
0 <= targetFriend <= n - 1
Each arrival_i time is distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the party second-by-second. It iterates through time from the earliest arrival to the latest departure, processing any arrivals or departures that occur at each time step.

Algorithm

Initialize a map arrivals to store friend information (leaving_time, friend_index) keyed by their arrival_time.
Initialize another map departures to store lists of chairs that become free, keyed by leaving_time.
Initialize a min-priority queue availableChairs to manage unoccupied chairs and a counter nextChair for new chairs.
Find the maximum event time maxTime from the input.
Loop through time t from 1 to maxTime: a. Check departures for time t. Add any freed chairs to availableChairs. b. Check arrivals for time t. If a friend arrives: i. Assign a chair: poll from availableChairs or use nextChair++. ii. If the friend is targetFriend, return the assigned chair. iii. Schedule the departure by adding the chair and leaving time to the departures map.

Walkthrough

This method simulates the process chronologically by iterating through time from 1 up to the maximum possible event time. We use data structures to keep track of arrivals and departures scheduled for each time unit.

We use a hash map arrivals where arrivals.get(t) gives the friend arriving at time t and their leaving time. Another hash map departures maps a leaving time t to a list of chairs that become free at that time. A min-priority queue, availableChairs, keeps track of all unoccupied chairs, ensuring we can always find the one with the smallest number. A counter next_chair_num tracks the next new chair to be used if no freed chairs are available.

The simulation proceeds in a loop from t = 1 to the maximum time. At each time t, we first process departures by checking the departures map and adding any freed chairs to availableChairs. Then, we process arrivals. If a friend arrives, we assign them a chair from availableChairs or a new one. We record the assignment and schedule their departure. If the arriving friend is the targetFriend, we have found our answer and can return it.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5import java.util.PriorityQueue;6 7class Solution {8    public int smallestChair(int[][] times, int targetFriend) {9        int maxTime = 0;10        for (int[] time : times) {11            maxTime = Math.max(maxTime, time[1]);12        }13 14        Map<Integer, int[]> arrivals = new HashMap<>();15        for (int i = 0; i < times.length; i++) {16            arrivals.put(times[i][0], new int[]{times[i][1], i});17        }18 19        Map<Integer, List<Integer>> departures = new HashMap<>();20        PriorityQueue<Integer> availableChairs = new PriorityQueue<>();21        int nextChair = 0;22 23        for (int t = 1; t <= maxTime; t++) {24            if (departures.containsKey(t)) {25                for (int chair : departures.get(t)) {26                    availableChairs.offer(chair);27                }28                departures.remove(t);29            }30 31            if (arrivals.containsKey(t)) {32                int[] arrivalInfo = arrivals.get(t);33                int leavingTime = arrivalInfo[0];34                int friendIndex = arrivalInfo[1];35 36                int chairToAssign;37                if (!availableChairs.isEmpty()) {38                    chairToAssign = availableChairs.poll();39                } else {40                    chairToAssign = nextChair++;41                }42 43                if (friendIndex == targetFriend) {44                    return chairToAssign;45                }46 47                departures.computeIfAbsent(leavingTime, k -> new ArrayList<>()).add(chairToAssign);48            }49        }50        return -1; // Should not be reached51    }52}

Complexity

Time

O(T_max + N log N). The main loop runs T_max times. The total work for priority queue operations over the entire simulation is O(N log N).

Space

O(N + T_max), where N is the number of friends and T_max is the maximum leaving time. The maps for arrivals and departures can store up to T_max entries.

Trade-offs

Pros

Conceptually simple as it directly models the flow of time.

Cons

Inefficient time complexity if the time range is much larger than the number of friends.
High space complexity due to maps that can scale with the maximum time.

This is a more efficient approach that processes events (friend arrivals) in chronological order, jumping from one event time to the next. It avoids iterating through empty time intervals. By sorting friends based on their arrival times and using priority queues, we can efficiently manage chair allocation.

Algorithm

Create an augmented data structure to store [arrival, leaving, original_index] for each friend.
Sort this structure based on arrival times to process events chronologically.
Initialize two min-priority queues: available_chairs for free chair numbers, and occupied_chairs for [leaving_time, chair_number] pairs, sorted by leaving time.
Initialize a nextChair counter to 0.
Iterate through the sorted friends: a. For the current friend's arrival_time, free up chairs by moving them from occupied_chairs to available_chairs if their leaving_time is less than or equal to the arrival_time. b. Assign a chair: poll from available_chairs. If empty, use nextChair and increment it. c. If the current friend is the targetFriend, return the assigned chair number. d. Add the [leaving_time, assigned_chair] pair to occupied_chairs.

Walkthrough

This approach improves upon brute-force by only considering time points where an event (a friend arriving) occurs. This avoids wasteful iteration over empty time intervals.

First, we augment the times array to include the original index of each friend, creating entries of the form [arrival, leaving, original_index]. This is crucial for identifying the targetFriend after sorting. We then sort this augmented array based on arrival times.

We use two min-priority queues to manage the state of the chairs:

available_chairs: Stores integers representing chair numbers that are free. Polling from this gives the smallest-numbered available chair.
occupied_chairs: Stores pairs of [leaving_time, chair_number], ordered by leaving_time. This allows us to efficiently find which chairs become free next.

We iterate through the sorted friends. For each arriving friend, we first process all departures that have occurred up to the current friend's arrival time. We do this by checking the top of occupied_chairs and moving any freed chairs to available_chairs. Then, we assign the smallest available chair to the new arrival. If the arriving friend is our target, we return their assigned chair number. Otherwise, we add their chair and leaving time to the occupied_chairs queue.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public int smallestChair(int[][] times, int targetFriend) {6        int n = times.length;7        int[][] friends = new int[n][3];8        for (int i = 0; i < n; i++) {9            friends[i][0] = times[i][0]; // arrival10            friends[i][1] = times[i][1]; // leaving11            friends[i][2] = i;           // original index12        }13 14        Arrays.sort(friends, (a, b) -> Integer.compare(a[0], b[0]));15 16        PriorityQueue<Integer> availableChairs = new PriorityQueue<>();17        PriorityQueue<int[]> occupiedChairs = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));18        19        int nextChair = 0;20 21        for (int[] friend : friends) {22            int arrival = friend[0];23            int leaving = friend[1];24            int index = friend[2];25 26            while (!occupiedChairs.isEmpty() && occupiedChairs.peek()[0] <= arrival) {27                int[] freed = occupiedChairs.poll();28                availableChairs.offer(freed[1]);29            }30 31            int chairToAssign;32            if (!availableChairs.isEmpty()) {33                chairToAssign = availableChairs.poll();34            } else {35                chairToAssign = nextChair++;36            }37 38            if (index == targetFriend) {39                return chairToAssign;40            }41 42            occupiedChairs.offer(new int[]{leaving, chairToAssign});43        }44 45        return -1; // Should not be reached46    }47}

Complexity

Time

O(N log N). Sorting the N friends takes O(N log N). The loop processes each friend once, and the total time for all priority queue operations is also O(N log N).

Space

O(N), where N is the number of friends. We need O(N) space for the augmented friend data and for the priority queues.

Trade-offs

Pros

Optimal time complexity, independent of the time range.
Efficient space usage.

Cons

Slightly more complex to implement due to managing friend indices and multiple data structures.

Solutions

Solution

1/** * @param {number[][]} times * @param {number} targetFriend * @return {number} */ var smallestChair =2  function (times, targetFriend) {3    const n = times.length;4    const idle = new MinPriorityQueue();5    const busy = new MinPriorityQueue({ priority: (v) => v[0] });6    for (let i = 0; i < n; ++i) {7      times[i].push(i);8      idle.enqueue(i);9    }10    times.sort((a, b) => a[0] - b[0]);11    for (const [arrival, leaving, i] of times) {12      while (busy.size() > 0 && busy.front().element[0] <= arrival) {13        idle.enqueue(busy.dequeue().element[1]);14      }15      const j = idle.dequeue().element;16      if (i === targetFriend) {17        return j;18      }19      busy.enqueue([leaving, j]);20    }21  };

1class Solution {2public3  int smallestChair(int[][] times, int targetFriend) {4    int n = times.length;5    int[][] ts = new int[n][3];6    PriorityQueue<Integer> q = new PriorityQueue<>();7    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b)->a[0] - b[0]);8    for (int i = 0; i < n; ++i) {9      ts[i] = new int[]{times[i][0], times[i][1], i};10      q.offer(i);11    }12    Arrays.sort(ts, (a, b)->a[0] - b[0]);13    for (int[] t : ts) {14      int a = t[0], b = t[1], i = t[2];15      while (!busy.isEmpty() && busy.peek()[0] <= a) {16        q.offer(busy.poll()[1]);17      }18      int c = q.poll();19      if (i == targetFriend) {20        return c;21      }22      busy.offer(new int[]{b, c});23    }24    return -1;25  }26}

1using pii = pair < int , int > ; class Solution { public: int smallestChair ( vector < vector < int >>& times , int targetFriend ) { priority_queue < int , vector < int > , greater < int >> q ; priority_queue < pii , vector < pii > , greater < pii >> busy ; int n = times . size (); for ( int i = 0 ; i < n ; ++ i ) { times [ i ]. push_back ( i ); q . push ( i ); } sort ( times . begin (), times . end ()); for ( auto & t : times ) { int a = t [ 0 ], b = t [ 1 ], i = t [ 2 ]; while ( ! busy . empty () && busy . top (). first <= a ) { q . push ( busy . top (). second ); busy . pop (); } int c = q . top (); q . pop (); if ( i == targetFriend ) return c ; busy . push ({ b , c }); } return - 1 ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem