The Number of the Smallest Unoccupied Chair

Medium

Google

3 views

Topics:

ArraysGreedy Algorithms

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.

What is the chair number that the targetFriend will sit on?

The Number of the Smallest Unoccupied Chair

Medium

Google

3 views

Topics:

ArraysGreedy Algorithms

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.

What is the chair number that the targetFriend will sit on?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the arrival and leaving times?
Can arrival and leaving times overlap, and if so, how should that be handled?
Is it guaranteed that the target friend will always attend the meeting?
What is the expected return value if there are no unoccupied chairs when the target friend arrives?
How many friends will be attending the meeting (what is the maximum number of elements in the input arrays)?

Brute Force Solution

Approach

The goal is to find the smallest available chair number for a friend. We'll try assigning chairs one by one, starting from the smallest, until we find an empty one for our friend. We'll need to keep track of which chairs are taken.

Here's how the algorithm would work step-by-step:

Start checking chair numbers, beginning with chair number zero.
For each chair number, see if it is currently occupied (if someone is already sitting there).
If the chair is occupied, move on to the next chair number and repeat the check.
If the chair is not occupied, this is the smallest available chair for our friend.
Assign this chair to our friend and stop looking.

Code Implementation

def find_smallest_unoccupied_chair(occupied_chairs):
    chair_number = 0

    while True:
        # Check if the current chair is occupied.
        if chair_number not in occupied_chairs:

            # If the chair is not occupied, return the chair number.
            return chair_number

        # Move to the next chair number.
        chair_number += 1

#The following is an example of how the function would be invoked.
#occupied_chairs = [0,1,2,3,5]
#smallest_available_chair = find_smallest_unoccupied_chair(occupied_chairs)
#print(smallest_available_chair)

Big(O) Analysis

Time Complexity

O(n) – The described algorithm iterates through chair numbers, starting from 0, until it finds an unoccupied chair. In the worst-case scenario, the algorithm might need to check up to n chairs, where n represents the chair number assigned to the last seated person, before finding an available one. Therefore, the time complexity depends on the maximum occupied chair number. The number of operations scales linearly with the maximum chair number checked, making the time complexity O(n).

Space Complexity

O(N) – The provided plain English explanation implies keeping track of occupied chairs. This would require an auxiliary data structure, such as a boolean array or hash set, to represent whether each chair is occupied. In the worst case, we might need to check chairs up to a number N, where N represents the chair number we assign to our friend. Therefore, the space used by the algorithm grows linearly with N. The auxiliary space is thus O(N).

Optimal Solution

Approach

The key to solving this problem efficiently is to keep track of which chairs are available and quickly find the smallest available one. We can accomplish this using a data structure that helps us efficiently manage available and occupied chairs.

Here's how the algorithm would work step-by-step:

First, record the time someone arrives at and leaves the party, along with who they are.
Sort all these arrival and departure events by time.
Maintain a collection of available chairs, always keeping track of the smallest unoccupied chair.
Go through the events in sorted order. If someone arrives, assign them the smallest available chair from the collection of free chairs. Then remove that chair from the available chairs.
If someone leaves, mark their chair as available and add it to the collection of free chairs.
When you reach the arrival event for the person we are interested in, the chair number assigned at that time is the answer.

Code Implementation

import heapq

def smallest_unoccupied_chair(
        arrival_times: list[list[int]], target_friend: int) -> int:
    events = []
    for index, arrival_time in enumerate(arrival_times):
        events.append((arrival_time[0], 'arrival', index))
        events.append((arrival_time[1], 'departure', index))

    events.sort()

    available_chairs = []
    heapq.heappush(available_chairs, 0)
    assigned_chairs = {}

    for time, event_type, person_index in events:
        if event_type == 'arrival':
            # Assign the smallest available chair.
            chair_number = heapq.heappop(available_chairs)
            assigned_chairs[person_index] = chair_number

            if person_index == target_friend:
                return chair_number

            # Ensure that there is always a next smallest available chair.
            if not available_chairs:
                heapq.heappush(available_chairs,
                               chair_number + 1)

        else:
            # Free up the chair when someone leaves.
            chair_to_release = assigned_chairs[person_index]
            heapq.heappush(available_chairs, chair_to_release)

Big(O) Analysis

Time Complexity

O(n log n) – The solution involves sorting a list of arrival and departure events, which takes O(n log n) time, where n is the total number of events (arrivals and departures). The use of a data structure (like a min-heap or a TreeSet) to maintain available chairs allows for finding the smallest unoccupied chair and adding/removing chairs in O(log n) time per event. Since we iterate through each of the n events, this contributes another O(n log n) to the overall time complexity. Therefore, the total time complexity is dominated by O(n log n) + O(n log n), which simplifies to O(n log n).

Space Complexity

O(N) – The algorithm stores arrival and departure events in a list, which can grow up to a size proportional to the number of people (N) at the party. The 'available chairs' collection will, in the worst case, also need to store chair numbers for all N individuals if they all leave at different times. Therefore, the auxiliary space used by these data structures scales linearly with N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty arrivals and departures arrays	Return 0 as no seats are occupied yet, and the target friend needs chair 0.
Target friend arrives and departs at the same time as another friend	The solution should handle ties consistently (e.g., by arrival time) to determine seat assignment.
Arrival and departure times are very close together	Ensure the algorithm correctly handles cases where seats are freed up almost immediately after being occupied.
Large number of friend arrivals and departures	Consider the scalability of the solution; using a priority queue or set is crucial for performance.
Target friend arrives first	The target friend should be assigned chair 0 if no one is occupying chairs before their arrival.
Target friend arrives last, and all chairs before k are occupied	The algorithm should correctly find the smallest available chair, which will be k or higher.
Arrival and departure times are the same value for multiple friends	The solution should consistently handle the order of processing these simultaneous events.
Integer overflow potential with large arrival and departure times	Use appropriate data types (e.g., long) to prevent potential integer overflows in time calculations.