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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Number of the Smallest Unoccupied Chair

Difficulty: Medium

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. When a friend leaves the party, their chair becomes unoccupied at the moment they leave. You are given a 0-indexed 2D integer array times where times[i] = [arrival_i, leaving_i], indicating the arrival and leaving times of the i-th friend respectively, and an integer targetFriend. Return the chair number that the friend numbered targetFriend will sit on.

Key Insights

  • Friends arrive at distinct times and sit in the lowest-numbered unoccupied chair.
  • Chairs become available immediately after a friend leaves.
  • The problem can be solved using a priority queue or a min-heap to manage available chairs efficiently.
  • A mapping of chair assignments to friends is necessary to track which chair each friend occupies.

Space and Time Complexity

Time Complexity: O(n log n) - Sorting the arrival and leaving events takes O(n log n), and handling each event takes O(log n) due to the priority queue operations. Space Complexity: O(n) - We need space to store the priority queue and additional structures to track chair assignments.

Solution

To solve this problem, we will simulate the arrival and departure of friends using a priority queue (min-heap) to keep track of the next available chair. We will create a list of events consisting of both arrival and leaving times, processing them in chronological order. When a friend arrives, we will assign them the smallest available chair. When a friend leaves, we will add their chair back to the available chairs. This way, we can efficiently determine which chair the target friend occupies.

Code Solutions

import heapq

def smallestChair(times, targetFriend):
    events = []
    
    # Create a list of events for arrivals and departures
    for i, (arrival, leaving) in enumerate(times):
        events.append((arrival, i, 'arrive'))
        events.append((leaving, i, 'leave'))
    
    # Sort events by time; if times are the same, prioritize departures
    events.sort(key=lambda x: (x[0], x[2] == 'arrive'))
    
    available_chairs = []
    occupied_chairs = {}
    
    for time, friend, event_type in events:
        if event_type == 'arrive':
            # Assign the smallest available chair or the next chair if none are available
            if available_chairs:
                chair = heapq.heappop(available_chairs)
            else:
                chair = len(occupied_chairs)  # The next available chair number
            
            occupied_chairs[friend] = chair
            
            # If this is the target friend, return their chair number
            if friend == targetFriend:
                return chair
        else:  # event_type == 'leave'
            # The friend leaves, make their chair available again
            chair = occupied_chairs.pop(friend)
            heapq.heappush(available_chairs, chair)
← Back to All Questions