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 target_friend, return the chair number that target_friend 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.

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 (available_chairs) to track free chairs and another (occupied_chairs) 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 occupied_chairs and release any chairs that are now free. The friend then takes the smallest available chair—either from available_chairs if there are free ones or by taking a new chair if all are occupied. This chair assignment is recorded in occupied_chairs 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:

  • available_chairs 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.

  • occupied_chairs heap: This heap stores pairs of ( leaving_time, chair_index), 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 available_chairs, 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 available_chairs.

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

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

  • When target_friend 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: