We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Number of the Smallest Unoccupied Chair

Number: 2054

Difficulty: Medium

Paid? No

Companies: Amazon, Google, spinny, Microsoft, Bloomberg

Problem Description

There is a party where n friends (numbered 0 to n-1) arrive and depart at specified times. There is an infinite row of chairs numbered from 0 upward. As each friend arrives, they take the unoccupied chair with the smallest number. When a friend leaves, their chair becomes free immediately and can be occupied by any friend arriving exactly at that time. Given the arrival and leaving times for all friends, determine the chair number that the targetFriend will occupy.

Key Insights

  • The process can be viewed as a simulation of events (arrivals and departures) in increasing time order.
  • Use a min-heap (priority queue) to efficiently track the smallest available chair number.
  • Maintain another min-heap to track occupied chairs along with their leave times.
  • Before processing an arrival event, free up all chairs whose leaving time is less than or equal to the current arrival time.
  • The target friend’s arrival should be handled in the same way as others; just record which chair they get assigned.

Space and Time Complexity

Time Complexity: O(n log n) – due to sorting events and operations on heaps. Space Complexity: O(n) – for storing events and heaps.

Solution

We sort friends by their arrival times and simulate the arrival and departure events using two heaps. One heap maintains the currently occupied chairs (with their leave times and chair numbers) and the other maintains the available (free) chairs. At each arrival, we free all chairs that are now unoccupied. The friend takes the smallest numbered free chair. Special care is taken to update the targetFriend’s assignment when they arrive.

Code Solutions

Below are code solutions with detailed inline comments in Python, JavaScript, C++, and Java.

import heapq

def smallestChair(times, targetFriend):
    n = len(times)
    # Prepare a list of (arrival_time, leave_time, friend_index)
    events = [(times[i][0], times[i][1], i) for i in range(n)]
    # Sort friends by arrival time
    events.sort(key=lambda x: x[0])
    
    # Heap for available chairs; initially all chairs start as free.
    free_chairs = list(range(n))
    heapq.heapify(free_chairs)
    
    # Heap for occupied chairs, storing (leave_time, chair_number)
    occupied = []
    
    # Process each friend in order of arrival time.
    for arrival, leave, friend_idx in events:
        # Free up chairs from friends who have left.
        while occupied and occupied[0][0] <= arrival:
            leave_time, chair = heapq.heappop(occupied)
            heapq.heappush(free_chairs, chair)
        
        # Assign the friend the smallest available chair.
        chair_assigned = heapq.heappop(free_chairs)
        
        # If this friend is the target, return the assigned chair.
        if friend_idx == targetFriend:
            return chair_assigned
        
        # Add the chair to the occupied heap with the friend's leaving time.
        heapq.heappush(occupied, (leave, chair_assigned))
        
    return -1  # Should not reach here if inputs are valid.

# Example usage:
print(smallestChair([[1,4],[2,3],[4,6]], 1))  # Output: 1
← Back to All Questions