The Number of the Smallest Unoccupied Chair
There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.
- For example, if chairs
0,1, and5are occupied when a friend comes, they will sit on chair number2.
When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.
You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the i^th friend respectively, and an integer targetFriend. All arrival times are distinct.
Return the chair number that the friend numbered targetFriend will sit on.
Example 1
Input
times = [[1,4],[2,3],[4,6]], targetFriend = 1Output
1Friend 1 arrives at time 2 and sits on chair 1, so the answer is 1.
Example 2
Input
times = [[3,10],[1,5],[2,6]], targetFriend = 0Output
2Friend 0 arrives at time 3 after friends 1 and 2 have taken chairs 0 and 1, so friend 0 sits on chair 2.
Constraints
- n == times.length
- 2 <= n <= 10^4
- times[i].length == 2
- 1 <= arrivali < leavingi <= 10^5
- 0 <= targetFriend <= n - 1
- Each arrivali time is distinct.