[LeetCode] 1353. Maximum Number of Events That Can Be Attended 最多可以参加的会议数目

You are 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. 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

Constraints:

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 10^5

这道题给了一堆活动，每个活动是由起始日期和结束日期确定的活动时间范围，现在说是只要在某个活动的时间范围内参加一天，就算参加了该活动，而且说明每天最多只能参加一个活动，问可以参加的最大的活动数。这里参考的是 lee215 大神的解法，使用的是一种贪婪算法 Greedy Algorithm 的思想，把所有活动按照起始时间进行排序，然后每天尽量先去参加结束时间靠前的活动，这样就可以尽可能多的参加不同的活动。这里使用一个优先队列来管理当前可参加的活动的结束时间，优先队列默认是大的在前面，这里改变一下，让小的在前面，即结束早的活动在前面。

题目中给定了活动日期的范围 [1, 1e5]，那么就可以遍历每一天，这里用一个变量i，表示当前处理到的活动在 events 数组中的位置（是排序后的 events）。对于当前的天数 d 来说，我们需要首先移除队列中已经过期的活动，即结束时间小于d的活动，可以用个 for 循环来移除。之后要将所有起始时间等于d的活动的结束时间都加到优先队列中。此时若优先队列中有值，说明此时有活动可以参加，就参加结束时间最早的那个活动，将队首元素移除，并且结果 res 自增1即可，参见代码如下：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int res = 0, i = 0, n = events.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        sort(events.begin(), events.end());
        for (int d = 1; d <= 1e5; ++d) {
            while (!pq.empty() && pq.top() < d) {
                pq.pop();
            }
            while (i < n && events[i][0] == d) {
                pq.push(events[i++][1]);
            }
            if (!pq.empty()) {
                pq.pop();
                ++res;
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1353

类似题目：

Maximum Number of Events That Can Be Attended II

Maximum Earnings From Taxi

Meeting Rooms III

参考资料：

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/solutions/510263/java-c-python-priority-queue/

LeetCode All in One 题目讲解汇总(持续更新中...)