The Number of the Smallest Unoccupied Chair

The problem describes a scenario where friends are arriving at a party and taking the lowest-numbered available chair. When a friend leaves, the chair becomes available again. We’re interested in finding out which chair a specific friend (targetFriend) will sit in.

We can solve this problem by using a priority queue (heap) to keep track of available chairs, and an event-driven approach to simulate the arrivals and departures.

Here’s the Python code to achieve this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import heapq

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        events = []
        # Create events for arrivals and departures
        for i, (arrival, leaving) in enumerate(times):
            events.append((arrival, 1, i))  # Arrival event
            events.append((leaving, -1, i))  # Departure event

        # Sort events by time
        events.sort()

        # Available chairs, initially all chairs are available
        available_chairs = [i for i in range(len(times))]
        heapq.heapify(available_chairs)

        # Chair assignment for each friend
        chair_assignment = [0] * len(times)

        # Simulate the events
        for time, event_type, friend in events:
            if event_type == 1:  # Arrival
                chair = heapq.heappop(available_chairs)
                chair_assignment[friend] = chair
                if friend == targetFriend:
                    return chair
            else:  # Departure
                chair = chair_assignment[friend]
                heapq.heappush(available_chairs, chair)

        return -1  # This should never be reached

This code sets up a simulation where friends arrive and depart, and chairs are assigned and released as needed. The result for the target friend’s chair is returned as soon as they arrive at the party.