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 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.length
2 <= n <= 104
times[i].length == 2
1 <= arrivali < leavingi <= 105
0 <= targetFriend <= n - 1
- Each
arrivali
time is distinct.
Solution: Treeset + Simulation
Use a treeset to track available chairs, sort events by time.
note: process leaving events first.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: int smallestChair(vector<vector<int>>& times, int targetFriend) { const int n = times.size(); vector<pair<int, int>> arrival(n); vector<pair<int, int>> leaving(n); for (int i = 0; i < n; ++i) { arrival[i] = {times[i][0], i}; leaving[i] = {times[i][1], i}; } vector<int> pos(n); iota(begin(pos), end(pos), 0); // pos = [0, 1, ..., n -1] set<int> aval(begin(pos), end(pos)); sort(begin(arrival), end(arrival)); sort(begin(leaving), end(leaving)); for (int i = 0, j = 0; i < n; ++i) { const auto [t, u] = arrival[i]; while (j < n && leaving[j].first <= t) aval.insert(pos[leaving[j++].second]); aval.erase(pos[u] = *begin(aval)); if (u == targetFriend) return pos[u]; } return -1; } }; |