Solution: The Number of the Smallest Unoccupied Chair

Explore how to utilize min heaps to efficiently assign the smallest available chair to friends arriving and leaving at various times. This lesson teaches how to manage chair allocation dynamically by tracking free and occupied chairs with priority queues. You will learn to handle sorting, heap operations, and the logic to quickly find a target friend's chair in O(n log n) time, enhancing your problem-solving skills for interval and scheduling challenges.

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 ...