Leetcode Daily Question 11/10/2024 - 1942. The Number of the Smallest Unoccupied Chair

Problem Description:

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.

from typing import List
class Solution:
  def smallestChair(self, times: List[List[int]]) -> int:
    states = []
    for i, (arrival, leave) in enumerate(times):
      states.append(arrival, i, "arrival")
      states.append(leave, i, "leave")
      
    next_chair = 0
    n = len(times)
    occupied = [-1] * n
   	vacant = []
    heapq.heapify(vacant)
    
    for time, index, state in states:
      if state == "arrival":
        if vacant:
          chair = heapq.heappop(vacant)
        else:
          chair = next_chair 
          next_chair += 1
        
        occupied[index] = chair
        if index == targetFriend:
          return chair
      
      elif state == "leave":
        heapq.heappush(vacant, occupied[index])
        
    return -1

Explanation:

To solve this, we first need to sort all event in chronological order. We sort by arrival time, except when a friend leaves as another arrives. In that case, we deal with the leaving friend first, allowing the seat to be immediately taken up by the new comer.

Then we use a min heap to keep track of the chairs that are left vacant when a friend leaves. This makes sure that the small chair is always on the top of the heap.

Additionally, we use a next chair variable to assign the next smallest chair when a friend arrives and no one has left / no one has arrived yet.

Finally, we use an occupied array to know which friend is occupying which chair at any point in time.

def smallestChair(times):
  states = []
  for i, (arrival, leave) in enumerate(times):
    state.append((arrival, i, "arrival"))
    state.append((leave, i, "leave"))
    
  states.sort(key = lambda x: (x[0], x[2] == "leave")
    
  n = len(times)
  occupied = [-1] * n
  next_chair = 0
  vacant = []
  heapq.heapify(vacant)
  
  for time, index, state in states:
    if state == "arrival":
      if vacant:
        chair = heapq.heappop(vacant)
      else:
        chair = next_chair
        next_chair += 1
        
      occupied[index] = chair
      if index == targetFriend:
        return chair
      
    elif state == "leave":
      heapq.heappush(vacant, occupied[index])
      
  return -1

The time complexity Is O(n log n). Creating the states array takes O(n) time, whiles sorting the states array takes O(n log n) time based on Python’s modified quick sort. Traversing the states array takes O(n) time. So O(n log n) dominates.

The space complexity is O(n) as we store each of the arrival and leaving time of each friend. The min heap and occupancy array also have O(n) space.

The full solution can be found near the top of the page.