Show problems as
Classic problem #1942MediumArrayHash TableHeap (Priority Queue)

The Number of the Smallest Unoccupied Chair

Real-world version: The Seat the Watched Guest Takes
Tracked in this browser only
Read The Number of the Smallest Unoccupied Chair on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A waiting room has an endless run of seats numbered 0, 1, 2 and onwards. visits[i] = [arrives, leaves] says when guest i comes in and when they go.

A guest coming in takes the free seat with the smallest number. A seat falls free the moment its guest goes, so a guest arriving exactly then may take it.

No two guests arrive at the same moment. Return the number of the seat taken by guest watched.

Examples

Example 1

Input
visits = [[1, 2], [2, 3], [3, 4]], watched = 2
Output
0

Each guest goes exactly as the next comes in, so seat 0 is free every time and everyone sits there.

Example 2

Input
visits = [[1, 10], [2, 10]], watched = 1
Output
1

Both guests stay until the same moment, so the second has to take the next seat up.

Example 3

Input
visits = [[1, 100], [2, 5], [3, 4], [6, 50]], watched = 3
Output
1

By the time the last guest arrives, seats 1 and 2 have both fallen free, and the smaller number wins even though seat 2 fell free first.

Constraints

  • 2 <= visits.length <= 10^4
  • visits[i].length == 2
  • 1 <= visits[i][0] <= visits[i][1] <= 10^5
  • visits[i][0] < visits[i][1]
  • 0 <= watched <= visits.length - 1
  • no two guests arrive at the same moment

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_chair(visits: list[list[int]], watched: int) -> int:
Java
public int smallestChair(int[][] visits, int watched)

More on the same topics