Solution: The Number of the Smallest Unoccupied Chair

Explore an algorithm that uses min heaps to assign the smallest unoccupied chair to arriving friends at a party. Understand how to manage chair availability dynamically by processing arrival and leaving times, optimizing with heaps for efficient retrieval and release. This lesson shows how to implement the solution with O(n log n) time complexity, preparing you to solve similar interview coding challenges involving dynamic resource allocation.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

At a party, $n$ friends, numbered from $0$ to $n - 1$ , arrive and leave at different times. There are infinitely many chairs, numbered $0$ onwards. Each arriving friend sits on the smallest available chair at that moment.

For example, if chairs $0$ , $1$ , and $5$ are occupied when a friend arrives, they will sit on chair number $2$ .

When a friend leaves, their chair becomes immediately available. If another friend arrives simultaneously, they can take that chair.

You are given a $0$ -indexed $2D$ list ...