# The Number of the Smallest Unoccupied Chair
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair)
Canonical: https://scaleengineer.com/dsa/problems/the-number-of-the-smallest-unoccupied-chair
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [Otter.ai](https://scaleengineer.com/companies/otter.ai)
---
## 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] = [arrivali, leavingi]`, indicating the arrival and leaving times of the `ith` 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 <= 104`
* `times[i].length == 2`
* `1 <= arrivali < leavingi <= 105`
* `0 <= targetFriend <= n - 1`
* Each `arrivali` time is **distinct**.

# Approaches
## Brute-Force Simulation by Time Iteration
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int maxTime = 0;
        for (int[] time : times) {
            maxTime = Math.max(maxTime, time[1]);
        }

        Map<Integer, int[]> arrivals = new HashMap<>();
        for (int i = 0; i < times.length; i++) {
            arrivals.put(times[i][0], new int[]{times[i][1], i});
        }

        Map<Integer, List<Integer>> departures = new HashMap<>();
        PriorityQueue<Integer> availableChairs = new PriorityQueue<>();
        int nextChair = 0;

        for (int t = 1; t <= maxTime; t++) {
            if (departures.containsKey(t)) {
                for (int chair : departures.get(t)) {
                    availableChairs.offer(chair);
                }
                departures.remove(t);
            }

            if (arrivals.containsKey(t)) {
                int[] arrivalInfo = arrivals.get(t);
                int leavingTime = arrivalInfo[0];
                int friendIndex = arrivalInfo[1];

                int chairToAssign;
                if (!availableChairs.isEmpty()) {
                    chairToAssign = availableChairs.poll();
                } else {
                    chairToAssign = nextChair++;
                }

                if (friendIndex == targetFriend) {
                    return chairToAssign;
                }

                departures.computeIfAbsent(leavingTime, k -> new ArrayList<>()).add(chairToAssign);
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
1.  Initialize a map `arrivals` to store friend information (`leaving_time`, `friend_index`) keyed by their `arrival_time`.
2.  Initialize another map `departures` to store lists of chairs that become free, keyed by `leaving_time`.
3.  Initialize a min-priority queue `availableChairs` to manage unoccupied chairs and a counter `nextChair` for new chairs.
4.  Find the maximum event time `maxTime` from the input.
5.  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.

## Optimized Event-Driven Simulation with Priority Queues
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int n = times.length;
        int[][] friends = new int[n][3];
        for (int i = 0; i < n; i++) {
            friends[i][0] = times[i][0]; // arrival
            friends[i][1] = times[i][1]; // leaving
            friends[i][2] = i;           // original index
        }

        Arrays.sort(friends, (a, b) -> Integer.compare(a[0], b[0]));

        PriorityQueue<Integer> availableChairs = new PriorityQueue<>();
        PriorityQueue<int[]> occupiedChairs = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        
        int nextChair = 0;

        for (int[] friend : friends) {
            int arrival = friend[0];
            int leaving = friend[1];
            int index = friend[2];

            while (!occupiedChairs.isEmpty() && occupiedChairs.peek()[0] <= arrival) {
                int[] freed = occupiedChairs.poll();
                availableChairs.offer(freed[1]);
            }

            int chairToAssign;
            if (!availableChairs.isEmpty()) {
                chairToAssign = availableChairs.poll();
            } else {
                chairToAssign = nextChair++;
            }

            if (index == targetFriend) {
                return chairToAssign;
            }

            occupiedChairs.offer(new int[]{leaving, chairToAssign});
        }

        return -1; // Should not be reached
    }
}
```
### Algorithm
1.  Create an augmented data structure to store `[arrival, leaving, original_index]` for each friend.
2.  Sort this structure based on arrival times to process events chronologically.
3.  Initialize two min-priority queues: `available_chairs` for free chair numbers, and `occupied_chairs` for `[leaving_time, chair_number]` pairs, sorted by leaving time.
4.  Initialize a `nextChair` counter to 0.
5.  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`.

# Solutions
### JavaScript

```javascript
/** * @param {number[][]} times * @param {number} targetFriend * @return {number} */ var smallestChair =
  function (times, targetFriend) {
    const n = times.length;
    const idle = new MinPriorityQueue();
    const busy = new MinPriorityQueue({ priority: (v) => v[0] });
    for (let i = 0; i < n; ++i) {
      times[i].push(i);
      idle.enqueue(i);
    }
    times.sort((a, b) => a[0] - b[0]);
    for (const [arrival, leaving, i] of times) {
      while (busy.size() > 0 && busy.front().element[0] <= arrival) {
        idle.enqueue(busy.dequeue().element[1]);
      }
      const j = idle.dequeue().element;
      if (i === targetFriend) {
        return j;
      }
      busy.enqueue([leaving, j]);
    }
  };

```

### Java

```java
class Solution {
public
  int smallestChair(int[][] times, int targetFriend) {
    int n = times.length;
    int[][] ts = new int[n][3];
    PriorityQueue<Integer> q = new PriorityQueue<>();
    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b)->a[0] - b[0]);
    for (int i = 0; i < n; ++i) {
      ts[i] = new int[]{times[i][0], times[i][1], i};
      q.offer(i);
    }
    Arrays.sort(ts, (a, b)->a[0] - b[0]);
    for (int[] t : ts) {
      int a = t[0], b = t[1], i = t[2];
      while (!busy.isEmpty() && busy.peek()[0] <= a) {
        q.offer(busy.poll()[1]);
      }
      int c = q.poll();
      if (i == targetFriend) {
        return c;
      }
      busy.offer(new int[]{b, c});
    }
    return -1;
  }
}

```

### CPP

```cpp
using 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 ; } };
```

### Python

```python
class Solution:
    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

```