1942. The Number of the Smallest Unoccupied Chair


Problem Description

Imagine attending a party with a never-ending row of seats, where each friend chooses the first available seat to sit down. When a friend leaves, their seat becomes available for the next person who shows up. Everyone arrives and leaves the party at specific times. For instance, if friend 0 occupies chairs 0, 1, and 5, the next arriving friend will take seat 2. Now, we have a list detailing the arrival and departure times for each friend, and our goal is to find out which chair a particular friend (referred to as targetFriend) will occupy.

Intuition

To determine which seat targetFriend takes, we need to:

  1. Keep track of all available chairs and occupied chairs at any given time.
  2. Assign the lowest available chair number to each friend on arrival.
  3. Release the chair when a friend leaves, making it available for new arrivals.

We can achieve this using a min-heap to represent the available chairs, ensuring we always get the lowest numbered chair. Another min-heap is used to manage occupied chairs, where the key is the leaving time. We keep track of friends' arriving and leaving times, and we check the availability of chairs at each arrival. When a friend leaves, we release their chair and put it back into the heap of available chairs.

When the targetFriend arrives, we extract the lowest available chair number from the heap and return it, as this is the chair they will occupy.

The process looks like this:

  1. Initialize a min-heap with all possible chair numbers.
  2. Sort the list of friends by arrival time so that we assign chairs in the order friends arrive.
  3. Initialize a second min-heap to manage occupied chairs, sorted by leaving time.
  4. Iterate over the sorted list, and at each friend's arrival:
    • Release the chairs of friends who have left (leaving time is less than or equal to the current arrival time).
    • Extract the next available chair from the min-heap of available chairs.
    • If the current friend is targetFriend, return the chosen chair number.
    • Add the current friend's chair and leaving time to the min-heap of occupied chairs.

By utilizing two heaps, we efficiently manage the incoming and outgoing friends and their chair selections in a way that fulfills all the constraints of the given problem.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution is centered around efficiently tracking and managing available and occupied chairs using heaps. Here's how the provided solution works:

  1. Initialization of the Min-Heaps:

    • We create a min-heap h representing all possible chair numbers. Initially, this heap contains all numbers from 0 to n-1, because there are n friends and hence at most n chairs that could be occupied at once.
    • We use the heapq library's heapify method to transform the list of chair numbers into a min-heap.
    • A second min-heap busy is used to track occupied chairs, with leaving times as keys, so we know when chairs become available.
  2. Annotating Times with Indices:

    • We append each friend's index to their respective [arrival, leaving] times to keep a mapping of which friend is associated with which time slot.
  3. Sorting Based on Arrival Times:

    • We then sort the times array by arrival times. Sorting is necessary to simulate the chronological order of events as friends arrive and depart.
  4. Iterating Over Sorted Times:

    • We loop through each friend's arrival (a) and departure (b) times (after annotating them with the friend's index i):
      • For each arriving friend, we check if there are any occupied chairs that have become available (i.e., the current time is greater than or equal to the leaving time of some friends). This is done by checking the busy heap.
      • If there are such chairs, we push them back to the h heap of available chairs.
  5. Allocating Chairs & Handling targetFriend:

    • We pop the lowest number from the h heap which represents the currently available chair with the smallest number.
    • If the index i of the currently arriving friend is equal to targetFriend, we return the chair number immediately since this is the chair targetFriend will sit on.
    • If not, we push the friend's chair along with their leaving time to the busy heap, indicating that this chair is now occupied until the leaving time.
  6. Returning the Chair Number:

    • The loop continues until targetFriend is encountered. When targetFriend arrives, their chair number is returned.

The algorithm effectively uses min-heaps to ensure that we always allocate the smallest available chair number and free chairs up in the order people leave. By maintaining two separate heaps—one for available chairs sorted by chair number and another for busy (occupied) chairs sorted by leaving times—we ensure an efficient and orderly management of arriving and departing friends.

Notice that the solution has a fail-safe return value of -1, which is a pattern often used in functions to indicate that for some reason, no valid result was computed. However, in the context of this problem, this line is never reached because it is guaranteed that targetFriend will eventually arrive and be assigned a chair.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's illustrate the solution approach with a simple example. Suppose we have 4 friends with the following arrival and departure times and we want to find the chair number for targetFriend identified by index 2:

  • Friend 0: Arrives at 1, leaves at 4
  • Friend 1: Arrives at 2, leaves at 5
  • Friend 2: Arrives at 6, leaves at 9 (targetFriend)
  • Friend 3: Arrives at 3, leaves at 7
  1. Initialization of the Min-Heaps: We begin by initializing a min-heap h with chair numbers [0, 1, 2, 3]. The busy min-heap is initialized and empty because no friends have arrived yet.

  2. Annotating Times with Indices: We modify the times list to include each friend's index:

    • Friend 0: [1, 4, 0]
    • Friend 1: [2, 5, 1]
    • Friend 2: [6, 9, 2] (targetFriend)
    • Friend 3: [3, 7, 3]
  3. Sorting Based on Arrival Times: We sort the list based on arrival times:

    • Friend 0: [1, 4, 0]
    • Friend 1: [2, 5, 1]
    • Friend 3: [3, 7, 3]
    • Friend 2: [6, 9, 2] (targetFriend)
  4. Iterating Over Sorted Times:

    • At time 1, friend 0 arrives. We pop 0 from h, and push [4, 0] onto busy.
    • At time 2, friend 1 arrives. We pop 1 from h, and push [5, 1] onto busy.
    • At time 3, friend 3 arrives. We pop 2 from h, and push [7, 2] onto busy.
    • Time 4 arrives, friend 0's leaving time. We pop [4, 0] from busy and push 0 back onto h.
    • We continue like this until all friends have arrived and left or until the targetFriend arrives.
  5. Allocating Chairs & Handling targetFriend:

    • When targetFriend (index 2) arrives at time 6, friends 0 and 1 have left, freeing chairs 0 and 1. Since 0 is the lowest number in h, we pop it and assign it to the index 2 friend.
    • We return the chair number 0 for the targetFriend because they are the next to arrive.

This example navigates through the arrival and departure of friends, effectively managing chair allocations using two heaps and efficiently identifies the chair number for the targetFriend, which is 0 in this scenario.

Solution Implementation

1import heapq
2
3class Solution:
4    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
5        # Number of friends (or chairs needed)
6        num_friends = len(times)
7      
8        # Initialize the heaps for available chairs and chairs currently taken
9        available_chairs = list(range(num_friends))
10        heapq.heapify(available_chairs)
11        occupied_chairs = []
12      
13        # Add the friend's index to each arrival and leaving time
14        for friend_index in range(num_friends):
15            times[friend_index].append(friend_index)
16      
17        # Sort the times based on arrival times
18        times.sort()
19      
20        # Iterate over each friend's time
21        for arrival, departure, friend_index in times:
22            # Free up chairs if current time is past the departure time of any friend
23            while occupied_chairs and occupied_chairs[0][0] <= arrival:
24                chair_num = heapq.heappop(occupied_chairs)[1]
25                heapq.heappush(available_chairs, chair_num)
26          
27            # Assign the smallest available chair to the current friend
28            current_chair = heapq.heappop(available_chairs)
29          
30            # If the current friend is the target friend, return the chair number
31            if friend_index == targetFriend:
32                return current_chair
33          
34            # Mark the chair as occupied until departure
35            heapq.heappush(occupied_chairs, (departure, current_chair))
36
37        # If the target friend's chair was not found, return -1 (though this should never happen)
38        return -1
39
1class Solution {
2  
3    public int smallestChair(int[][] times, int targetFriend) {
4      
5        // Number of friends
6        int numFriends = times.length;
7      
8        // Enhanced array to store arrival and leaving times along with friend's index
9        int[][] events = new int[numFriends][3];
10      
11        // Priority queue to manage available chairs by smallest index
12        PriorityQueue<Integer> availableChairs = new PriorityQueue<>();
13      
14        // Priority queue to manage busy chairs. Orders by end time of usage.
15        PriorityQueue<int[]> occupiedChairs = new PriorityQueue<>((a, b) -> a[0] - b[0]);
16      
17        // Initialize available chairs and events array
18        for (int i = 0; i < numFriends; ++i) {
19            events[i] = new int[]{ times[i][0], times[i][1], i };
20            availableChairs.offer(i);
21        }
22      
23        // Sort events by arrival times
24        Arrays.sort(events, (a, b) -> a[0] - b[0]);
25      
26        // Iterate over all events
27        for (int[] event : events) {
28            int arrivalTime = event[0];
29            int leavingTime = event[1];
30            int friendIndex = event[2];
31          
32            // Release all chairs that are free by the current arrival time
33            while (!occupiedChairs.isEmpty() && occupiedChairs.peek()[0] <= arrivalTime) {
34                availableChairs.offer(occupiedChairs.poll()[1]);
35            }
36          
37            // Assign the smallest available chair
38            int assignedChair = availableChairs.poll();
39          
40            // If the current friend is the target friend, return the chair number
41            if (friendIndex == targetFriend) {
42                return assignedChair;
43            }
44          
45            // Mark the chair as occupied until leavingTime
46            occupiedChairs.offer(new int[]{leavingTime, assignedChair});
47        }
48      
49        // If the chair wasn't found (which shouldn't happen), return -1
50        return -1;
51    }
52}
53
1#include <vector>
2#include <queue>
3#include <algorithm>
4using namespace std;
5
6// Define a readable alias for the pair<int, int> type
7using Pair = pair<int, int>;
8
9class Solution {
10public:
11    int smallestChair(vector<vector<int>>& times, int targetFriend) {
12        // Min-heap to keep track of available chairs
13        priority_queue<int, vector<int>, greater<int>> availableChairs;
14      
15        // Min-heap to keep track of occupied chairs, sorted by the time they will become free
16        priority_queue<Pair, vector<Pair>, greater<Pair>> occupiedChairs;
17      
18        int numberOfFriends = times.size();
19      
20        // Initialize the available chairs heap with consecutive chair numbers
21        for (int i = 0; i < numberOfFriends; ++i) {
22            times[i].push_back(i);  // Append the original index to the times array
23            availableChairs.push(i);  // Mark the chair as available
24        }
25      
26        // Sort the times array by arrival time
27        sort(times.begin(), times.end());
28      
29        // Iterate through each friend's time
30        for (auto& time : times) {
31            int arriveTime = time[0], leaveTime = time[1], index = time[2];
32          
33            // Release chairs that have become free before the current friend's arrival
34            while (!occupiedChairs.empty() && occupiedChairs.top().first <= arriveTime) {
35                // Add the chair to the available chairs heap
36                availableChairs.push(occupiedChairs.top().second);
37                occupiedChairs.pop();  // Remove it from the occupied chairs heap
38            }
39          
40            // Take the smallest available chair number
41            int chair = availableChairs.top();
42            availableChairs.pop();
43          
44            // If the current friend is the target friend, return the chair number
45            if (index == targetFriend) {
46                return chair;
47            }
48          
49            // Mark the chair as occupied until the leave time
50            occupiedChairs.push({leaveTime, chair});
51        }
52      
53        // This return is a fallback, the function should have returned from the loop
54        return -1;
55    }
56};
57
1// Import necessary functionalities from TypeScript standard library
2import { PriorityQueue } from './path/to/priorityQueue'; // Replace with actual import path
3
4// Define a readable type alias for the pair [number, number]
5type Pair = [number, number];
6
7// Min-heap to keep track of available chairs
8let availableChairs = new PriorityQueue<number>((a, b) => a - b);
9
10// Min-heap to keep track of occupied chairs, sorted by the time they will become free
11let occupiedChairs = new PriorityQueue<Pair>((a, b) => a[0] - b[0]);
12
13// Function to find the smallest chair for the target friend
14function smallestChair(times: number[][], targetFriend: number): number {
15    times.map((time, index) => [...time, index]) // Append the original index to the times array
16        .sort((a, b) => a[0] - b[0]) // Sort the times array by arrival time
17        .forEach(time => {
18            let [arriveTime, leaveTime, index] = time;
19
20            // Release chairs that have become free before the current friend's arrival
21            while (!occupiedChairs.isEmpty() && occupiedChairs.peek()[0] <= arriveTime) {
22                availableChairs.add(occupiedChairs.poll()[1]); // Add the chair to the available chairs queue
23            }
24
25            // Initialize available chairs with consecutive chair numbers if not already added
26            if (availableChairs.isEmpty()) {
27                for (let chair = 0; chair < times.length; chair++) {
28                    availableChairs.add(chair);
29                }
30            }
31          
32            // Take the smallest available chair number
33            let chair = availableChairs.poll();
34
35            // If the current friend is the target friend, return the chair number
36            if (index === targetFriend) {
37                return chair;
38            }
39          
40            // Mark the chair as occupied until the leave time
41            occupiedChairs.add([leaveTime, chair]);
42        });
43
44    // This return is a fallback, the function should have returned from the forEach loop
45    throw new Error("The target friend's chair was not found");
46}
47
48// Assuming PriorityQueue is a generic class you have defined or imported 
49// from a library that manages a priority queue for its elements.
50

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed as follows:

  1. The initial heapification of h which is a list of n different numbers has a time complexity of O(n).

  2. Sorting the times list, which has n elements, has a time complexity of O(n log n).

  3. The for loop iterates over each of the n elements of the times list. Inside the loop, operations related to heap operations (heappop and heappush) are performed. In the worst case, each operation can take O(log n).

The while loop will pop elements out of the busy heap and push them back into the h heap. Each of these operations takes O(log n). However, each chair becomes free at most once during the whole process, so the total number of heappush and heappop operations for the busy list will be O(n) across the entire runtime of the program.

Finally, we have the heappop from h and conditional heappush in the busy heap inside the for loop. Since this happens once per guest (n times in total), we can represent these operations as n * O(log n).

Therefore, the overall time complexity of the loop is O(n log n).

  1. Taking both sorting and heap operations into account, the overall time complexity of the entire function can be represented as O(n log n) because the sort dominates the O(n) initialization of the h heap.

Space Complexity

The space complexity of the provided code can be analyzed as follows:

  1. Auxiliary space for the h heap which stores at most n elements is O(n).

  2. The busy heap also, in the worst case, can grow up to O(n). However, because the heaps do not grow independently (when an element is removed from busy, it is added to h, and vice versa) and are bounded by the number of chairs n, we still represent the total space used by both heaps as O(n).

  3. We also made modifications to the times array, adding the index i, but this is still within the O(n) space usage because each sub-list is only extended by one element.

Therefore, the overall space complexity is O(n) due to the heap structures and times list modifications.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄