关于#算法#的问题，如何解决？

在学习算法过程中遇到一个题是一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。返回你可以参加的最大会议数目。我想知道的是大家解释一下贪心算法

写回答
好问题 0 提建议
关注问题
分享
邀请回答
编辑收藏删除
收藏举报

2条回答默认最新

肩匣与橘游戏开发领域新星创作者 2022-11-21 10:58

关注


class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        priority_queue<int,vector<int>, greater<int>> q;//小顶堆，结束时间早的，先出队
        int count = 0, i = 0, time = 0;
        while(i < events.size() || !q.empty())
        {
            time++;
            while(!q.empty() && q.top() < time)//结束时间过去了，该会议删除
                q.pop();
            while(i < events.size() && events[i][0] == time)
            {
                q.push(events[i][1]);//time时间，会议i开始了，把他的结束时间push进去
                i++;
            }
            if(!q.empty())
            {
                count++;
                q.pop();//最早结束的先参加
            }
        }
        return count;
    }
};