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.