The Number Of The Smallest Unoccupied Chair - Leetcode Solution

The problem "The Number Of The Smallest Unoccupied Chair" on LeetCode asks us to find the number of the smallest unoccupied chair given the arrival and departure times of multiple people. The arrival and departure times are given in two separate arrays, and we need to assume that all people enter and leave the room in sequential order. We can assume that there are always enough chairs for everyone.

Algorithm

The algorithm for solving the problem can be as follows:

1. Create two arrays arr and dep of the same length n, where n is the number of people.

2. Iterate through the arrival times and for each arrival time, find the first unoccupied chair by iterating through the chairs and checking if the corresponding element in the boolean array chairs is False. If a chair is found, mark it as occupied by setting the corresponding element in chairs to True, and record the arrival time and chair number in arr.

3. Iterate through the departure times and for each departure time, find the corresponding chair number in arr and set its departure time to the current departure time.

4. Iterate again through the arrival times and for each arrival time, find the corresponding chair number in arr and check if its departure time is earlier than the current arrival time. If so, mark the chair as unoccupied by setting the corresponding element in chairs to False.

5. Iterate through the chairs, find the first unoccupied chair and return its number.

Code

Here's the Python code that implements the above algorithm:

def smallestChair(times: List[List[int]], targetFriend: int) -> int: arr = [] dep = [] chairs = [False] * 10001

for i in range(len(times)):
    found = False
    for j in range(len(chairs)):
        if not chairs[j]:
            arr.append([times[i][0], j])
            chairs[j] = True
            found = True
            break
    
    if not found:
        arr.append([-1, -1])
    
for i in range(len(times)):
    for j in range(len(arr)):
        if arr[j][1] == -1:
            continue
        
        if times[i][0] == arr[j][0] and times[i][1] == arr[j][1]:
            dep.append([times[i][2], j])
            break
    
arr = sorted(arr, key=lambda x: x[0])

for i in range(len(times)):
    for j in range(len(arr)):
        if arr[j][1] == -1:
            continue
        
        if times[i][0] == arr[j][0] and times[i][1] == arr[j][1]:
            for k in range(len(dep)):
                if dep[k][1] == j and dep[k][0] < times[i][2]:
                    chairs[arr[j][1]] = False
            break
    
for i in range(len(chairs)):
    if not chairs[i]:
        return i

The time complexity of the algorithm is O(n^2) because of the nested loops. However, since n <= 10^4, the algorithm should run reasonably fast.

1