{x}
blog image

The Number of the Smallest Unoccupied Chair

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.

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.

 

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

 

Constraints:

  • n == times.length
  • 2 <= n <= 104
  • times[i].length == 2
  • 1 <= arrivali < leavingi <= 105
  • 0 <= targetFriend <= n - 1
  • Each arrivali time is distinct.

Solution Explanation: 1942. The Number of the Smallest Unoccupied Chair

This problem involves assigning chairs to friends arriving and leaving a party, aiming to find the chair number assigned to a specific target friend. The most efficient approach uses priority queues (min-heaps).

Approach:

  1. Data Preprocessing:

    • Augment the times array by adding a friend's index to each element: [arrival_time, leaving_time, friend_index]. This allows us to track which friend is associated with each arrival and departure.
    • Sort the augmented times array based on arrival times. This ensures we process friends in the order they arrive.

  2. Priority Queues:

    • idle: A min-heap storing the chair numbers that are currently unoccupied. Initially, it contains chairs 0 to n-1 (where n is the number of friends).
    • busy: A min-heap storing tuples of (leaving_time, chair_number). This helps us efficiently track when chairs become free. The priority is the leaving_time, ensuring that chairs are released in the order they become available.

  3. Iteration and Assignment:

    • Iterate through the sorted times array. For each friend:
      • Free up chairs: Remove all entries from busy where the leaving_time is less than or equal to the current friend's arrival_time. Add their chair numbers back to the idle heap.
      • Assign a chair: Get the smallest available chair number from the idle heap. This is the chair the current friend will occupy.
      • Check target: If the current friend's index is the targetFriend, return the assigned chair number.
      • Update busy: Add the (leaving_time, chair_number) tuple for the current friend to the busy heap.

  4. Return Value: The function returns the chair number assigned to the targetFriend.

Time and Space Complexity:

  • Time Complexity: O(n log n), where n is the number of friends. The sorting step takes O(n log n). Heap operations (insertion, deletion, peeking) take O(log n) each, and we perform these operations at most O(n) times.
  • Space Complexity: O(n). We use priority queues (idle and busy), both of which can hold at most O(n) elements.

Code Implementation (Python):

import heapq
 
class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        n = len(times)
        # Add friend indices to times array
        for i in range(n):
            times[i].append(i)
        # Sort by arrival times
        times.sort()
        # Initialize heaps
        idle = list(range(n))
        heapq.heapify(idle)
        busy = []
        # Iterate through friends
        for arrival, leaving, i in times:
            # Free up chairs
            while busy and busy[0][0] <= arrival:
                heapq.heappush(idle, heapq.heappop(busy)[1])
            # Assign chair
            chair = heapq.heappop(idle)
            if i == targetFriend:
                return chair
            # Update busy heap
            heapq.heappush(busy, (leaving, chair))

The implementations in other languages (Java, C++, Go, TypeScript, JavaScript) follow the same logic, but use their respective language's priority queue/heap implementations. The core algorithmic idea remains consistent across all languages.