> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# The Number of the Smallest Unoccupied Chair

> Tested Python solution for LeetCode 1942 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 1942, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/smallest-unoccupied-chair/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1942   # by problem number
lcpy gen -s smallest_unoccupied_chair   # by problem name
```

## 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<sub>i</sub>, leaving<sub>i</sub>]`, indicating the arrival and leaving times of the i\<sup>th\</sup> friend respectively, and an integer `targetFriend`. All arrival times are distinct.

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

### Examples

```
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.
```

```
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^4
* times\[i].length == 2
* 1 \<= arrivali \< leavingi \<= 10^5
* 0 \<= targetFriend \<= n - 1
* Each arrivali time is distinct.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/smallest_unoccupied_chair/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/smallest_unoccupied_chair/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def smallest_chair(self, times: list[list[int]], target_friend: int) -> int:
        free: list[int] = []
        leaving: list[tuple[int, int]] = []
        next_chair = 0
        for i in sorted(range(len(times)), key=lambda idx: times[idx][0]):
            arrive = times[i][0]
            while leaving and leaving[0][0] <= arrive:
                heapq.heappush(free, heapq.heappop(leaving)[1])
            if free:
                chair = heapq.heappop(free)
            else:
                chair = next_chair
                next_chair += 1
            if i == target_friend:
                return chair
            heapq.heappush(leaving, (times[i][1], chair))
        return -1
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.