1942 The Number of the Smallest Unoccupied Chair

Problem Statement

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

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

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

Instructions

• You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

• Return the chair number that the friend numbered targetFriend will sit on.

For the whole problem statement, please refer here.

Plans

• We need to process the arrivals in chronological order. This can be done by sorting the arrival times along with the friend incides.

• Use a mini-heap to keep track of the smallest available chair. This will allow us to efficiently find the next available chair when a friend arrives.

• Use another min-heap to keep track of chairs that are currently occupied, sorted by the time they will be freed. This helps in efficiently handling departures.

• Process each arrival in order, updating the state of the chairs and tracking which chair the target friend will sit on.

Solution

from heapq import heappush, heappop

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # Create a list of tuples (arrival_time, friend_index) and sort it by arrival_time
        arrivals = [(time[0], i) for i, time in enumerate(times)]
        arrivals.sort()  
        # Initialize a list of available chairs from 0 to len(times) -1
        available_chairs = [i for i in range(len(times))]
        # Initialize a list to keep track of occupied chairs
        occupied = []  
        
        # Process the arrival event 
        for arrival_time, friend in arrivals:
            # Free up chairs that are no longer occupied
            while occupied and occupied[0][0] <= arrival_time:
                _, chair = heappop(occupied)
                heappush(available_chairs, chair)
            
            # Assign the smallest available chair to the friend
            chair = heappop(available_chairs)
            # Mark the chair as occupied with the friend's leaving time
            heappush(occupied, (times[friend][1], chair))
            
            # If the current friend is the target friend, return the assigned chair
            if friend == targetFriend:
                return chair
        
        # If the the target friend is not found (which should not happen), return -1
        return -1  

Explanation

1. Sorting Arrivals

   • We create a list of tuples arrivals where each tuple in (arrival_time, friend_index). This helps us process arrivals in chronological order.

   • We sort the arrivals list based on the arrival times.

2. Min-Heap for Available Chairs

   • We initialize a list available_chairs with chair numbers from 0 in n-1. This list will be used as a min-heap to quickly find the smallest available chair.

3. Tracking Occupied Chairs

   • We use another list occupied to keep track of chairs that are currently occupied. This list will be used as a min-heap sorted by the leaving times of the friends occupying the chairs.

4. Processing Arrivals

   • For each arrival events (arrival_time, friend), we first free up any chairs that are no longer occupied by checking the occupied heap. If the earliest leaving time in the occupied heap is less than or equal to the current arrival time, we pop those chairs from the occupied heap and push them back to the available_chairs heap.

   • We then assign the smallest available chair to the friend by popping from the available_chairs heap.

   • We push the assigned chair to the occupied heap with the leaving time of the friend.

   • If the current friend is the targetFriend, we return the assigned chair number.

5. Returning the reuslt

   • If we successfully process all arrivals and find the chair for the targetFriend, we return that chair number. If for some reason the target friend is not found (which should not happen given the problem constraints), we return -1.