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, and 5 are occupied when a friend comes, they will sit on chair number 2.
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 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.length2 <= n <= 104times[i].length == 21 <= arrivali < leavingi <= 1050 <= targetFriend <= n - 1- Each
arrivali time is distinct.
Solutions
Solution 1: Priority Queue (Min-Heap)
First, we create a tuple for each friend consisting of their arrival time, leaving time, and index, then sort these tuples by arrival time.
We use a min-heap idle to store the currently available chair numbers. Initially, we add 0, 1, …, n-1 to idle. We also use a min-heap busy to store tuples (leaving, chair), where leaving represents the leaving time and chair represents the chair number.
We iterate through each friend's arrival time, leaving time, and index. For each friend, we first remove all friends from busy whose leaving time is less than or equal to the current friend's arrival time, and add their chair numbers back to idle. Then we pop a chair number from idle, assign it to the current friend, and add (leaving, chair) to busy. If the current friend's index is equal to targetFriend, we return the assigned chair number.
The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the number of friends.
PythonJavaC++GoTypeScriptJavaScript
class Solution:
def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
n = len(times)
for i in range(n):
times[i].append(i)
times.sort()
idle = list(range(n))
heapify(idle)
busy = []
for arrival, leaving, i in times:
while busy and busy[0][0] <= arrival:
heappush(idle, heappop(busy)[1])
j = heappop(idle)
if i == targetFriend:
return j
heappush(busy, (leaving, j))(code-box)
class Solution {
public int smallestChair(int[][] times, int targetFriend) {
int n = times.length;
PriorityQueue<Integer> idle = new PriorityQueue<>();
PriorityQueue<int[]> busy = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < n; ++i) {
times[i] = new int[] {times[i][0], times[i][1], i};
idle.offer(i);
}
Arrays.sort(times, Comparator.comparingInt(a -> a[0]));
for (var e : times) {
int arrival = e[0], leaving = e[1], i = e[2];
while (!busy.isEmpty() && busy.peek()[0] <= arrival) {
idle.offer(busy.poll()[1]);
}
int j = idle.poll();
if (i == targetFriend) {
return j;
}
busy.offer(new int[] {leaving, j});
}
return -1;
}
}(code-box)
class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> busy;
priority_queue<int, vector<int>, greater<int>> idle;
int n = times.size();
for (int i = 0; i < n; ++i) {
times[i].push_back(i);
idle.push(i);
}
ranges::sort(times);
for (const auto& e : times) {
int arrival = e[0], leaving = e[1], i = e[2];
while (!busy.empty() && busy.top().first <= arrival) {
idle.push(busy.top().second);
busy.pop();
}
int j = idle.top();
if (i == targetFriend) {
return j;
}
idle.pop();
busy.emplace(leaving, j);
}
return -1;
}
};(code-box)
func smallestChair(times [][]int, targetFriend int) int {
idle := hp{}
busy := hp2{}
for i := range times {
times[i] = append(times[i], i)
heap.Push(&idle, i)
}
sort.Slice(times, func(i, j int) bool { return times[i][0] < times[j][0] })
for _, e := range times {
arrival, leaving, i := e[0], e[1], e[2]
for len(busy) > 0 && busy[0].t <= arrival {
heap.Push(&idle, heap.Pop(&busy).(pair).i)
}
j := heap.Pop(&idle).(int)
if i == targetFriend {
return j
}
heap.Push(&busy, pair{leaving, j})
}
return -1
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
type pair struct{ t, i int }
type hp2 []pair
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool { return h[i].t < h[j].t || (h[i].t == h[j].t && h[i].i < h[j].i) }
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }(code-box)
function smallestChair(times: number[][], targetFriend: number): number {
const n = times.length;
const idle = new MinPriorityQueue<number>();
const busy = new PriorityQueue((a, b) => a[0] - b[0]);
for (let i = 0; i < n; ++i) {
times[i].push(i);
idle.enqueue(i);
}
times.sort((a, b) => a[0] - b[0]);
for (const [arrival, leaving, i] of times) {
while (busy.size() > 0 && busy.front()[0] <= arrival) {
idle.enqueue(busy.dequeue()[1]);
}
const j = idle.dequeue();
if (i === targetFriend) {
return j;
}
busy.enqueue([leaving, j]);
}
return -1;
}(code-box)
/**
* @param {number[][]} times
* @param {number} targetFriend
* @return {number}
*/
var smallestChair = function (times, targetFriend) {
const n = times.length;
const idle = new MinPriorityQueue();
const busy = new PriorityQueue((a, b) => a[0] - b[0]);
for (let i = 0; i < n; ++i) {
times[i].push(i);
idle.enqueue(i);
}
times.sort((a, b) => a[0] - b[0]);
for (const [arrival, leaving, i] of times) {
while (busy.size() > 0 && busy.front()[0] <= arrival) {
idle.enqueue(busy.dequeue()[1]);
}
const j = idle.dequeue();
if (i === targetFriend) {
return j;
}
busy.enqueue([leaving, j]);
}
};(code-box)
