# Daily Challenge 10/11/2024: The Number of the Smallest Unoccupied Chair

See the full problem statement on leetcode.

## Analysis

```
times = [[1,4], [2,3], [4,6]]
target = 1
- item: [1,4]
occupied: {0: 4}
- item: [2, 3] occupied: {0: 4, 1: 3}
```

```
times = [[3,10],[1,2], [1,3], [1,5],[2,6]]
taget = 0
sorted = [1,2],[1,3],[1,5],[2,6],[3,10]
- item: [1, 2]
occupied: {0: 2}
opened: {}
- item: [1, 3]
occupied: {0: 2, 1: 3}
opened: {}
- item: [1, 5]
occupied: {0: 2, 1: 3, 2: 5}
opened: {}
- item: [2, 6]
occupied: {0: 6, 1: 3, 2: 5}
opened: {0}
note: remove key 0 since its occupant has left
- item: [3, 10]
occupied: {0: 6, 1: 10, 2: 5} opened: {1}
```

Sort by arrival and create a hash table. Record the maximum seat occupied as -1.

For all items before arrival of the target:

- Remove entries in the hash table with the value of the current arrival. Put these values into a queue to be filled.
- If there are open seats fill the open seat of least value.

## Solution

My solution passed, but performed horribly due to its quadratic time complexity. It beat only \(5\%\) in run-time but \(60\%\) in memory. Here it is

```
class SolutionWorks:
def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
dict[int, int] = {}
occupied: = -1
last_time
= 0
final
for pos, (time, vacates) in sorted(
enumerate(times), key=lambda items: items[1][0]
):if time != last_time:
for k in list(occupied.keys()):
if occupied[k] <= time:
occupied.pop(k)
if len(occupied) != final:
= final
_seat_number for _seat_number in range(final):
if _seat_number not in occupied:
break
= _seat_number
seat_number else:
= final
seat_number += 1
final
if pos == targetFriend:
return seat_number
= vacates
occupied[seat_number] = time
last_time
return -1
```

I went ahead and read the editorial at this point and learned about min-heaps and noticed that this could optimize my current solution. Doing so only improved the runtime to beat about \(9\%\) and the memory to beat about \(78\%\).

```
class SolutionMinHeap:
def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
dict[int, int] = {}
occupied: list[int] = []
available: = -1
last_time
= 0
final
for pos, (time, vacates) in sorted(
enumerate(times), key=lambda items: items[1][0]
):if time != last_time:
for k in list(k for k, v in occupied.items() if v <= time):
occupied.pop(k)
heapq.heappush(available, k)
if available:
= heapq.heappop(available)
seat_number else:
= final
seat_number += 1
final
if pos == targetFriend:
return seat_number
= vacates
occupied[seat_number] = time
last_time
return -1
```

The obvious problem with the above solution is the time spent searching for values to remove from `occupied`

- this is why this solution has quadratic time complexity. The editorial solution solves this by breaking each event into arrival and leaving events. My rendition of this solution beat about \(38\%\) in runtime and \(60\%\) in memory.

```
class Solution:
def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
= []
events for index, (time_start, time_stop) in enumerate(times):
events.append([time_start, index])~index])
events.append([time_stop,
=lambda pair: pair[0])
events.sort(key
= list(range(len(times)))
vacant list[tuple[int, int]] = list()
occupied:
for time, pos in events:
# Mark all chairs as vacated for the friends which have left.
while occupied and occupied[0][0] <= time:
= heapq.heappop(occupied)
_, vacated_index
heapq.heappush(vacant, vacated_index)
# Mark chair occupied if the friend is ariving.
if pos > -1:
= heapq.heappop(vacant)
vacant_index 1], vacant_index))
heapq.heappush(occupied, (times[pos][
if pos == targetFriend:
return vacant_index
return -1
```