Given an array of events
where events[i] = [startDayi, endDayi]
. Every event i
starts at startDayi
and ends at endDayi
.
You can attend an event i
at any day d
where startTimei <= d <= endTimei
. Notice that you can only attend one event at any time d
.
Return the maximum number of events you can attend.
Example 1:
Input: events = [[1,2],[2,3],[3,4]] Output: 3 Explanation: You can attend all the three events. One way to attend them all is as shown. Attend the first event on day 1. Attend the second event on day 2. Attend the third event on day 3.
Example 2:
Input: events= [[1,2],[2,3],[3,4],[1,2]] Output: 4
Example 3:
Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]] Output: 4
Example 4:
Input: events = [[1,100000]] Output: 1
Example 5:
Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]] Output: 7
Constraints:
1 <= events.length <= 10^5
events[i].length == 2
1 <= events[i][0] <= events[i][1] <= 10^5
Solution: Greedy
Sort events by end time, for each event find the first available day to attend.
Time complexity: O(sum(endtime – starttime)) = O(10^10)
Space complexity: O(max(endtime – starttime) = O(10^5)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, 216 ms, 45.7 MB class Solution { public: int maxEvents(vector<vector<int>>& events) { sort(begin(events), end(events), [](const auto& a, const auto& b){ return a[1] < b[1]; }); int ans = 0; int seen[100001] = {0}; for (const auto& e : events) { for (int i = e[0]; i <= e[1]; ++i) { if (seen[i]) continue; ++seen[i]; ++ans; break; } } return ans; } }; |
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, 216 ms, 45.6 MB class Solution { public: int maxEvents(vector<vector<int>>& events) { sort(begin(events), end(events), [](const auto& a, const auto& b){ return a[1] < b[1]; }); int ans = 0; unsigned char seen[100000 / 8 + 1] = {0}; for (const auto& e : events) { for (int i = e[0]; i <= e[1]; ++i) { if (seen[i >> 3] & (1 << (i % 8))) continue; seen[i >> 3] |= 1 << (i % 8); ++ans; break; } } return ans; } }; |
Python
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua, 824 ms class Solution: def maxEvents(self, events: List[List[int]]) -> int: lo = min(e[0] for e in events) hi = max(e[1] for e in events) seen = [0] * (hi - lo + 1) for s, t in sorted(events, key=lambda e:e[1]): for i in range(s, t + 1): if seen[i - lo]: continue seen[i - lo] = 1 break return sum(seen) |
We can use a TreeSet to maintain the open days and do a binary search to find the first available day.
Time complexity: O(nlogd)
Space complexity: O(d)
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 27 |
// Author: Huahua, 416 ms, 46.1MB class Solution { public: int maxEvents(vector<vector<int>>& events) { sort(begin(events), end(events), [](const auto& a, const auto& b){ return a[1] < b[1]; }); int min_d = INT_MAX; int max_d = INT_MIN; for (const auto& e : events) { min_d = min(min_d, e[0]); max_d = max(max_d, e[1]); } vector<int> days(max_d - min_d + 1); iota(begin(days), end(days), min_d); set<int> s(begin(days), end(days)); // O(n) int ans = 0; for (const auto& e : events) { auto it = s.lower_bound(e[0]); if (it == end(s) || *it > e[1]) continue; s.erase(it); ++ans; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment