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 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
arrivalitime 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; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment