Welcome to Subscribe On Youtube
1942. The Number of the Smallest Unoccupied Chair
Description
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
, and5
are 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 0indexed 2D integer array times
where times[i] = [arrival_{i}, leaving_{i}]
, 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 = 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.
Example 2:
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.
Constraints:
n == times.length
2 <= n <= 10^{4}
times[i].length == 2
1 <= arrival_{i} < leaving_{i} <= 10^{5}
0 <= targetFriend <= n  1
 Each
arrival_{i}
time is distinct.
Solutions

class Solution { public int smallestChair(int[][] times, int targetFriend) { int n = times.length; int[][] ts = new int[n][3]; PriorityQueue<Integer> q = new PriorityQueue<>(); PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) > a[0]  b[0]); for (int i = 0; i < n; ++i) { ts[i] = new int[] {times[i][0], times[i][1], i}; q.offer(i); } Arrays.sort(ts, (a, b) > a[0]  b[0]); for (int[] t : ts) { int a = t[0], b = t[1], i = t[2]; while (!busy.isEmpty() && busy.peek()[0] <= a) { q.offer(busy.poll()[1]); } int c = q.poll(); if (i == targetFriend) { return c; } busy.offer(new int[] {b, c}); } return 1; } }

using pii = pair<int, int>; class Solution { public: int smallestChair(vector<vector<int>>& times, int targetFriend) { priority_queue<int, vector<int>, greater<int>> q; priority_queue<pii, vector<pii>, greater<pii>> busy; int n = times.size(); for (int i = 0; i < n; ++i) { times[i].push_back(i); q.push(i); } sort(times.begin(), times.end()); for (auto& t : times) { int a = t[0], b = t[1], i = t[2]; while (!busy.empty() && busy.top().first <= a) { q.push(busy.top().second); busy.pop(); } int c = q.top(); q.pop(); if (i == targetFriend) return c; busy.push({b, c}); } return 1; } };

class Solution: def smallestChair(self, times: List[List[int]], targetFriend: int) > int: n = len(times) h = list(range(n)) heapify(h) for i in range(n): times[i].append(i) times.sort() busy = [] for a, b, i in times: while busy and busy[0][0] <= a: heappush(h, heappop(busy)[1]) c = heappop(h) if i == targetFriend: return c heappush(busy, (b, c)) return 1