The Number of the Smallest Unoccupied Chair

lcpy gen -n 1942   # by problem number
lcpy gen -s smallest_unoccupied_chair   # by problem name

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation:
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation:
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

import heapq


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def smallest_chair(self, times: list[list[int]], target_friend: int) -> int:
        free: list[int] = []
        leaving: list[tuple[int, int]] = []
        next_chair = 0
        for i in sorted(range(len(times)), key=lambda idx: times[idx][0]):
            arrive = times[i][0]
            while leaving and leaving[0][0] <= arrive:
                heapq.heappush(free, heapq.heappop(leaving)[1])
            if free:
                chair = heapq.heappop(free)
            else:
                chair = next_chair
                next_chair += 1
            if i == target_friend:
                return chair
            heapq.heappush(leaving, (times[i][1], chair))
        return -1