leetcode 1353

问题

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:

img

1
2
3
4
5
6
7
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:

1
2
Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Example 3:

1
2
Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

Example 4:

1
2
Input: events = [[1,100000]]
Output: 1

Example 5:

1
2
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

分析

带有区间的问题往往先将区间按照左端点或者右部端点进行排序，然后执行贪心策略。我们首先将所有区间按照左端点（开始时间）从小到大进行排列，然后使用“日期”从左到右进行扫描。在所有可选择的事件中，我们应该选择截止时间最为接近的事件来进行处理，这也符合我们大部分人平时的做事习惯。于是，我们可以使用一个按照截止时间从小到大进行排序的优先队列来维护所有可选择的事件，每个“日子”从优先队列的队头选择一个事件进行处理。每次处理完之后要要更新日期为下一天，并对“可选择的事件”进行增减。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());   // vector<int> 有默认排序
        priority_queue<int, vector<int>, greater<int>> q;
        int day = 1;
        int i   = 0;
        int ans = 0;
        do {
            while (i < events.size() && events[i][0] <= day) {
                q.push(events[i][1]);
                ++i;
            }
            if (q.size() != 0) {
                ans ++ ;
                q.pop();
            }
            day++;
            while (q.size() != 0 && q.top() < day)
                q.pop();
        } while (q.size() != 0 || i < events.size());
        return ans;
    }
};