活动选择（贪心算法）

有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个 开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重 叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。

本题解法的关键在于找到一个比较方法，让这个比较方法尽可能多的安排活动，而要使活动尽可能的多，则每次选择活动结束时间最早的即可

#include
#include
#include
using namespace std;
struct cmp{bool operator()(vector&a1, vector&a2){return a1[1] < a2[1];}
};
int getNum(vector>events){sort(events.begin(), events.end(), cmp());int i = 0;int num = 1;for (int j = 1; j < events.size(); j++){if (events[j][0] >= events[i][1]){num++;i = j;}}return num;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！