LeetCode 1353. 最多可以参加的会议数目(贪心)

Ch_Zaqdt

发布于 2020-02-24 12:23:45

8790

发布于 2020-02-24 12:23:45

文章被收录于专栏：Zaqdt_ACM

题目链接：https://leetcode-cn.com/problems/maximum-number-of-events-that-can-be-attended/

这道题其实有好多类似的题，都是优先去找最左边的区间，又优先去挑选最右边的端点。所以对于这道题来说，如果现在是第idx天，那么最优的选的肯定是会议结束时间离idx最近的会议，大致思路就是这样，接下来会一点一点的讲解。

首先我们要先对原数组进行排序，按会议开始的时间从小到大排序。假如说现在是第一天，那么我们把其中所有在第一天开始的会议都挑出来，那么对于第一天来说肯定选择结束时间最早的是最优的(这一点不难理解吧)。为了更清晰一点，假如目前在第一天开始的会议有这么多个[[1,2],[1,3],[1,4],[1,8]]，那么对于第一天肯定选择[1,2]是最优的，那么还剩下[[1,3],[1,4],[1,8]]等到第二天再说。然后现在来到了第二天，我们依旧去把会议在第二天开始的都挑出来，假如有两个[[2,4],[2,5]]，那么再加上第一天剩下的三个，现在一共有5个[[1,3],[1,4],[1,8],[2,4],[2,5]](其实这里的[1,3],[1,4],[1,8]可以当作是[2,3],[2,4],[2,8])，那么对于这些我们肯定也是选择结束时间最靠前的，选择[1,3]，就这样以此类推，每天都选择结束时间最靠前的。

那么过程就是这么个过程，我们要怎么去实现呢？这里我用的是优先队列，当然也可以用set。用优先队列来维护第idx天所挑出来的会议，然后队列中按结束时间从小到大排序，每次选择结束时间最早的就好了。

AC代码：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int ans = 0;
        priority_queue<int, vector<int>, greater<int> > q;
        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b){
            return a[0] < b[0];             // 按左端点排序
        });
        int idx = 1;         // 表示当前的天数
        int i = 0;
        while(i < events.size() || q.size() != 0){
            while(i < events.size() && idx == events[i][0]){    // 将以第idx天开始的会议挑出来
                q.push(events[i][1]);
                i ++;
            }
            while(!q.empty()){
                if(q.top() < idx) q.pop();      // 如果结束时间超过了当前肯定就选不了了
                else {                          // 否则idx就在这个会议的区间中，符合条件
                    ans ++;
                    q.pop();
                    break;
                }
            }
            idx ++;
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/02/18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

set