Problem of The Day: The Number of the Smallest Unoccupied Chair

Problem Statement

Intuition

The problem revolves around assigning chairs to friends who arrive and leave at different times. The goal is to figure out which chair a particular friend (targetFriend) will sit on when they arrive. Each friend grabs the first available chair when they arrive, and the chair is freed when they leave.

The initial thought is to keep track of chair assignments and use a heap to efficiently manage available chairs as well as the times when chairs become free.

Approach

1. Sorting by Arrival Time: First, sort all friends by their arrival time, since chairs will be assigned in the order that they arrive.
2. Tracking Chair Usage: Use a min-heap (min_heap) to track when each chair becomes free, associating the leaving time of a friend with the chair they were using.
3. Available Chairs: Another min-heap (min_heap_chair) is used to track available chairs. Chairs are assigned based on the smallest available index (for example, chair 0 is assigned first, then chair 1, etc.).

4. Processing Friends: For each friend’s arrival:

   • Free up any chairs whose leaving time is less than or equal to the current arrival time.
   • Assign the smallest available chair to the current friend.
   • If the current friend is the targetFriend, return the chair they are assigned.

   This ensures that we efficiently manage chair assignments and free them up as soon as friends leave, using a priority queue (min-heap) to always allocate the smallest indexed chair.

Complexity

• Time complexity:
  Sorting the times list takes \(O(N \log N)\) where N is the number of friends.
  Processing each friend involves heap operations that take \(O(\log N)\) per operation, leading to a total of \(O(N \log N)\) for all chair assignments.

  Overall, the time complexity is \(O(N \log N)\).

• Space complexity:
  We use a heap to store available chairs and a heap for leaving times, both of size \(N\). Therefore, the space complexity is \(O(N)\).

Code

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        N = len(times)
        time_to_index = {tuple(time): i for i, time in enumerate(times)}
        sorted_time = sorted(times, key=lambda x: x[0])
        min_heap = []
        min_heap_chair = [i for i in range(N)]
        for i, [arrival, leaving] in enumerate(sorted_time):
            if targetFriend == time_to_index[tuple(sorted_time[i])]:
                while min_heap and min_heap[0][0] <= arrival:
                    _, chair = heapq.heappop(min_heap)
                    heapq.heappush(min_heap_chair, chair)
                return heapq.heappop(min_heap_chair)
            if not min_heap or min_heap[0][0] > arrival:
                used_chair = heapq.heappop(min_heap_chair)
                heapq.heappush(min_heap, [leaving, used_chair])
            else:
                while min_heap and min_heap[0][0] <= arrival:
                    _, available_chair = heapq.heappop(min_heap)
                    heapq.heappush(min_heap_chair, available_chair)
                chair = heapq.heappop(min_heap_chair)
                heapq.heappush(min_heap, [leaving, chair])

Editorial

Approach 2: Event-based with Two Priority Queues

class Solution:
    def smallestChair(self, times, targetFriend):
        events = []  # to store both arrival and leave events

        # populate events with arrival and leave times
        for i in range(len(times)):
            events.append([times[i][0], i])  # Arrival
            events.append([times[i][1], ~i])  # Leave

        events.sort()  # Sort events by time

        available_chairs = list(
            range(len(times))
        )  # Tracking chairs that are free

        occupied_chairs = []  # When each chair will be free

        for event in events:
            time, friend = event

            # free up chairs if friends leave
            while occupied_chairs and occupied_chairs[0][0] <= time:
                _, chair = heapq.heappop(
                    occupied_chairs
                )  # Pop chair that becomes empty
                heapq.heappush(available_chairs, chair)  # available chairs

            # If friend arrives
            if friend >= 0:
                chair = heapq.heappop(available_chairs)
                if friend == targetFriend:
                    return chair
                heapq.heappush(
                    occupied_chairs, [times[friend][1], chair]
                )  # chair will be occupied till this time

        return -1  # should not come to this point

Approach 3: Set with Sorted Insertion

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        target_arrival = times[targetFriend][0]
        times = sorted(
            [
                (arrival, leave, index)
                for index, (arrival, leave) in enumerate(times)
            ]
        )

        next_chair = 0
        available_chairs = []
        leaving_queue = []

        for time in times:
            arrival, leave, index = time

            # Free up chairs based on current time
            while leaving_queue and leaving_queue[0][0] <= arrival:
                _, chair = heapq.heappop(leaving_queue)
                heapq.heappush(available_chairs, chair)

            if available_chairs:
                current_chair = heapq.heappop(available_chairs)
            else:
                current_chair = next_chair
                next_chair += 1

            # Push current leave time and chair
            heapq.heappush(leaving_queue, (leave, current_chair))

            # Check if it's the target friend
            if index == targetFriend:
                return current_chair

        return 0