Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1942.html
1942. The Number of the Smallest Unoccupied Chair
Level
Medium
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 ith
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.
Solution
Use a tree set to store unoccupied chairs. Since there are n
friends, only the chairs numbered from 0 to n  1
are needed. Loop over all arrival times and leaving times in order. Each time a friend arrives, select the smallest element from the tree set and remove the smallest element from the tree set. Use a hash map to store the friend’s chair number. Each time a friend leaves, obtain the friend’s chair number from the hash map and add the chair number back to the tree set. When the friend numbered targetFriend
arrives, return the chair number of targetFriend
.

class Solution { public int smallestChair(int[][] times, int targetFriend) { PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() { public int compare(int[] pair1, int[] pair2) { int time1 = pair1[1], time2 = pair2[1]; if (Math.abs(time1) != Math.abs(time2)) return Math.abs(time1)  Math.abs(time2); else return time1  time2; } }); int length = times.length; for (int i = 0; i < length; i++) { int arrival = times[i][0], leaving = times[i][1]; priorityQueue.offer(new int[]{i, arrival}); priorityQueue.offer(new int[]{i, leaving}); } TreeSet<Integer> set = new TreeSet<Integer>(); for (int i = 0; i < length; i++) set.add(i); Map<Integer, Integer> seatMap = new HashMap<Integer, Integer>(); while (!priorityQueue.isEmpty()) { int[] pair = priorityQueue.poll(); int index = pair[0], time = pair[1]; if (time > 0) { int first = set.first(); set.remove(first); seatMap.put(index, first); if (index == targetFriend) return first; } else { int seat = seatMap.get(index); set.add(seat); } } return 1; } } ############ 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; } }

// OJ: https://leetcode.com/problems/thenumberofthesmallestunoccupiedchair/ // Time: O(NlogN) // Space: O(N) class Solution { public: int smallestChair(vector<vector<int>>& A, int targetFriend) { set<int> avail; // indices of available seats for (int i = 0; i < A.size(); ++i) avail.insert(i); auto target = A[targetFriend][0]; sort(begin(A), end(A)); auto cmp = [&](int a, int b) { return A[a][1] > A[b][1]; }; priority_queue<int, vector<int>, decltype(cmp)> pq(cmp); // min heap of indices of friends in seats. Friend at heap top has the earliest leave time unordered_map<int, int> seat; // mapping from friend index to seat index for (int i = 0; i < A.size(); ++i) { auto &v = A[i]; while (pq.size() && A[pq.top()][1] <= v[0]) { // given the current arrival time, pop all the friends that have left int s = seat[pq.top()]; avail.insert(s); // free the corresponding seat seat.erase(i); pq.pop(); } int s = *avail.begin(); // take the seat with the smallest index available if (v[0] == target) return s; avail.erase(s); seat[i] = s; pq.push(i); } 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 ############ # 1942. The Number of the Smallest Unoccupied Chair # https://leetcode.com/problems/thenumberofthesmallestunoccupiedchair class Solution: def smallestChair(self, times: List[List[int]], targetFriend: int) > int: n = len(times) available = list(range(n)) mp = collections.defaultdict(int) seats = [] for i, (t1,t2) in enumerate(times): seats.append((t1, 1, i)) seats.append((t2, 0, i)) seats.sort() for time, isArrival, friend in seats: if isArrival: seat = heapq.heappop(available) if friend == targetFriend: return seat mp[friend] = seat else: seat = mp[friend] heapq.heappush(available, seat) return mp[targetFriend]