Solution: The Number of the Smallest Unoccupied Chair

Statement

At a party, $n$ friends, numbered from $0$ to $n - 1$, arrive and leave at different times. There are infinitely many chairs, numbered $0$ onwards. Each arriving friend sits on the smallest available chair at that moment.

For example, if chairs $0$, $1$, and $5$ are occupied when a friend arrives, they will sit on chair number $2$.

When a friend leaves, their chair becomes immediately available. If another friend arrives simultaneously, they can take that chair.

You are given a $0$-indexed $2D$ list times, where times[i] $= [ arrival_i, leaving_i]$ represents the arrival and departure times of the $i_{th}$ friend. All arrival times are unique.

Given an integer targetFriend, return the chair number that targetFriend will sit on.

Constraints:

• $n ==$ times.length

• times[i].length $== 2$

• $1\leq$ arrivali < leavingi $\leq 10^5$

• $0 \leq$ target_friend $\leq n - 1$

• Each arrivali time is unique.

Solution

As friends arrive, they always take the lowest-numbered unoccupied chair; when they leave, their chair becomes available for reuse. To efficiently manage this process, we maintain two min heaps: one (availableChairs) to track free chairs and another (occupiedChairs) to manage occupied chairs and their departure times.

We begin by sorting the friends based on their arrival times. As each friend arrives, we first check occupiedChairs and release any chairs that are now free. The friend then takes the smallest available chair—either from availableChairs if there are free ones or by taking a new chair if all are occupied. This chair assignment is recorded in occupiedChairs with the friend’s departure time.

A brute-force approach of checking each chair sequentially would be too slow, so we use min heaps (Priority Queues) for efficient retrieval of the smallest available chair and timely processing of departures. When the target friend is assigned a chair, we return it immediately and stop further processing.

Let’s look at the solution steps below:

• First, sort the times list based on each friend’s arrival time. This ensures that we process them in the correct order without manually searching for the next arriving friend.

• Initialize two min-heaps:

  • availableChairs heap: This heap stores the smallest available chair numbers. Whenever a new friend arrives, they take the smallest free chair in $O(log n)$ time.

  • occupiedChairs heap: This heap stores pairs of ( leavingTime, chairIndex), ensuring that chairs are released correctly as soon as a friend leaves.

• Iterate through the sorted list:

  • Before assigning a chair, check if any occupied chairs should be freed based on leaving times. The freed chair is added back to availableChairs, ensuring that the smallest-numbered chair is always available first.

  • Assign a chair to the arriving friend:

    • If there are free chairs, assign the smallest one from availableChairs.

    • Assign the next new chair and increment chairIndex if no chairs are available.

  • After assigning a chair, store it in occupiedChairs along with the friend’s leaving time. This ensures that the chair is released at the correct time and can be reused efficiently.

  • When targetFriend is assigned a chair, return the chair index immediately from the function to terminate further processing.

Let’s look at the following illustration to get a better understanding of the solution: