Problem Description

You have a party with n friends numbered from 0 to n - 1. The party venue has an infinite number of chairs numbered from 0 to infinity.

When a friend arrives at the party, they follow this rule: they sit on the unoccupied chair with the smallest number available. For example, if chairs 0, 1, and 5 are already occupied when a friend arrives, they will sit on chair 2 (the smallest unoccupied chair).

When a friend leaves the party, their chair immediately becomes available. If another friend arrives at the exact same moment someone leaves, the arriving friend can take that just-vacated chair.

You are given:

• A 2D array times where times[i] = [arrival_i, leaving_i] represents when the ith friend arrives and leaves
• An integer targetFriend indicating which friend you need to track
• All arrival times are distinct (no two friends arrive at the same time)

Your task is to determine which chair number the friend numbered targetFriend will sit on when they arrive.

The solution uses two min-heaps to efficiently track available and occupied chairs. The idle heap maintains available chair numbers in ascending order, while the busy heap tracks when chairs will become available again, sorted by leaving time. By processing friends in order of arrival time and updating chair availability accordingly, we can determine exactly which chair the target friend will occupy.

Intuition

The key insight is that we need to simulate the chair assignment process in chronological order of arrivals. Since friends always take the smallest available chair number, we need an efficient way to track which chairs are available at any given time.

Think about what happens at each arrival:

1. Some friends might have left, freeing up their chairs
2. The arriving friend needs the smallest available chair

This naturally leads to using a min-heap for available chairs - it gives us the smallest chair number in O(log n) time. But how do we know which chairs become free?

We realize that chairs become available based on leaving times. When a friend arrives, any friend who was supposed to leave before or at this arrival time will have freed their chair. This suggests we need another data structure to track occupied chairs by their "expiration time" (leaving time).

A second min-heap ordered by leaving time perfectly fits this need. At each arrival, we can efficiently check and remove all friends who have already left (those with leaving time ≤ current arrival time), returning their chairs to the available pool.

The elegant part is that we only need n chairs maximum (even though infinite chairs exist) because at most n friends can be at the party simultaneously. So we initialize our available chairs heap with just 0 to n-1.

By processing friends in arrival order and maintaining these two heaps - one for available chairs (smallest first) and one for when occupied chairs will be freed (earliest leaving time first) - we can efficiently simulate the entire party and find which chair our target friend sits on.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implementation follows these steps:

1. Data Preparation: First, we augment each friend's data with their index. For each friend i, we transform times[i] = [arrival, leaving] into [arrival, leaving, i]. This allows us to track which friend is which after sorting.

2. Sort by Arrival Time: We sort the augmented times array by arrival time. This ensures we process friends in the order they arrive at the party.

3. Initialize Data Structures:

   • Create a min-heap idle containing all chair numbers from 0 to n-1 using list(range(n)) and heapify(idle)
   • Create an empty min-heap busy to store (leaving_time, chair_number) tuples

4. Process Each Friend: Iterate through the sorted friends:

   a. Free Up Chairs: Before assigning a chair to the current friend, check if any previous friends have left:

   while busy and busy[0][0] <= arrival:
       heappush(idle, heappop(busy)[1])

   This removes all friends from busy whose leaving time is ≤ current arrival time, and returns their chairs to idle.

   b. Assign Chair: Pop the smallest available chair from idle:

   j = heappop(idle)

   c. Check Target: If this is our target friend, return the chair number:

   if i == targetFriend:
       return j

   d. Mark Chair as Busy: Otherwise, add this friend's leaving time and chair to busy:

   heappush(busy, (leaving, j))

The time complexity is O(n log n) due to sorting and heap operations. The space complexity is O(n) for the heaps. The algorithm efficiently simulates the chair assignment process while maintaining the invariant that friends always get the smallest available chair number.

Example Walkthrough

Let's walk through a concrete example to see how the two-heap solution works.

Example Input:

• times = [[1,4], [2,3], [4,6]] (3 friends)
• targetFriend = 1 (we want to know where friend 1 sits)

Step 1: Data Preparation We augment each friend's data with their index:

• Friend 0: [1, 4, 0] (arrives at 1, leaves at 4)
• Friend 1: [2, 3, 1] (arrives at 2, leaves at 3)
• Friend 2: [4, 6, 2] (arrives at 4, leaves at 6)

After sorting by arrival time, the order remains the same (already sorted).

Step 2: Initialize Heaps

• idle = [0, 1, 2] (all chairs initially available)
• busy = [] (no chairs occupied yet)

Step 3: Process Friends in Arrival Order

Time = 1 (Friend 0 arrives):

• Check busy heap: empty, so no chairs to free
• Pop smallest chair from idle: chair 0
• Friend 0 is not our target
• Push (4, 0) to busy (chair 0 will be free at time 4)
• State: idle = [1, 2], busy = [(4, 0)]

Time = 2 (Friend 1 arrives):

• Check busy heap: (4, 0) has leaving time 4 > 2, so no chairs freed
• Pop smallest chair from idle: chair 1
• Friend 1 IS our target! Return chair 1

Let's continue to see what would happen with Friend 2:

Time = 4 (Friend 2 arrives):

• Check busy heap: (4, 0) has leaving time 4 ≤ 4, so free chair 0
  • Pop (4, 0) from busy and push chair 0 to idle
• Check again: (3, 1) would have leaving time 3 ≤ 4, so free chair 1 too
  • Pop (3, 1) from busy and push chair 1 to idle
• State before assignment: idle = [0, 1, 2], busy = []
• Pop smallest chair from idle: chair 0
• Friend 2 sits on chair 0

Answer: Friend 1 sits on chair 1

This example demonstrates how:

• The idle heap always provides the smallest available chair
• The busy heap tracks when chairs become available again
• Chairs are reused once friends leave (Friend 2 gets chair 0 after Friend 0 leaves)
• The algorithm correctly handles the rule that friends take the smallest available chair

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by several operations:

• Adding indices to each time entry: O(n)
• Sorting the times array: O(n × log n)
• Heapifying the idle list: O(n)
• Main loop iterating through n friends: O(n)
  • Within each iteration:
    • While loop with heap operations: Each friend is pushed and popped from the busy heap at most once, so amortized O(log n) per iteration
    • Heap pop from idle: O(log n)
    • Heap push to busy: O(log n)

The overall complexity is O(n) + O(n × log n) + O(n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

The space complexity consists of:

• Modified times array with appended indices: O(n)
• idle heap containing up to n chair indices: O(n)
• busy heap containing at most n entries: O(n)

Total space used is O(n) + O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Track Original Friend Indices

One of the most common mistakes is sorting the times array by arrival time without preserving the original friend indices. After sorting, you lose track of which friend is which, making it impossible to identify when the targetFriend arrives.

Incorrect approach:

times.sort()  # Lost original indices!
for arrival, leaving in times:
    # Cannot determine if this is targetFriend

Correct approach:

# Add index before sorting
for i in range(n):
    times[i].append(i)
times.sort()
# Now we can check: if friend_index == targetFriend

2. Not Freeing Chairs at the Exact Arrival Time

A critical detail is that if a friend leaves at time t and another arrives at time t, the arriving friend CAN take the just-vacated chair. The condition for freeing chairs must use <= not <.

Incorrect:

while occupied_chairs and occupied_chairs[0][0] < arrival_time:  # Wrong!
    # This misses chairs that become available at exact arrival time

Correct:

while occupied_chairs and occupied_chairs[0][0] <= arrival_time:
    # Correctly frees chairs available at or before arrival

3. Using Too Many Chairs

Since we know there are exactly n friends and they can't all be present simultaneously (arrival times are distinct), we only need n chairs maximum. Creating an unnecessarily large chair pool wastes memory and time.

Inefficient:

available_chairs = list(range(10000))  # Wasteful!

Efficient:

available_chairs = list(range(n))  # Exactly what we need

4. Incorrect Heap Structure for Occupied Chairs

The occupied chairs heap must be ordered by leaving time (when the chair becomes free), not by chair number. Storing just chair numbers or using the wrong ordering breaks the logic.

Incorrect:

heapq.heappush(occupied_chairs, assigned_chair)  # No leaving time!
# or
heapq.heappush(occupied_chairs, (assigned_chair, leaving_time))  # Wrong order!

Correct:

heapq.heappush(occupied_chairs, (leaving_time, assigned_chair))
# Ensures we process by leaving time first