贪心算法之高级钟点秘书会议安排问题
发布时间
阅读量：
阅读量
该文本主要讨论如何在多个可能的会议上找到最多的非重叠时间段。通过贪心算法解决了这一问题：首先将所有会议按结束时间从小到大排序；然后依次选择最早结束且与已选会议不重叠的会议。这种方法确保了能在有限时间内召开尽可能多的会议。文中还出贪心策略是解决此类调度问题的关键方法论思想。
1、问题
即指年轻女性白领利用业余时间提供秘书服务并按小时计费
简而言之：最之间段内开最多的会议，但是会议和会议之间不能相交
2、分析
两个会议之间不能相交，不能有交集。
贪心算法：每一次从剩余会议中选择不冲突于已排布时间段且具有最早结束时间属性的会议安排。
具体来说我们首先将所有会议的结束时间按升序排列接着在每次选择时我们会考虑当前会议的结束时间和之后未被安排的会议并确保不会与后续会议重叠
3、代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int size = 1000;
struct Meet
{
//会议开始时间
int startTime;
//会议结束时间
int endTime;
//会议的序号
int num;
}data[size];
//按照结束时间从小到大排列
bool compare(struct Meet m1, struct Meet m2)
{
if (m1.endTime == m2.endTime)
return m1.startTime > m2.startTime;
else
return m1.endTime < m2.endTime;
}
class setMeet
{
public:
void init();
void resolve();
private:
//会议的个数和最多安排的次数
int all, count;
};
void setMeet::init()
{
std::cout << "请输入会议的个数" << std::endl;
std::cin >> all;
if (all <= 0)
{
std::cout << "您输入的数据有误" << std::endl;
}
std::cout << "您输入的会议个数为" << all << std::endl;
std::cout << "请输入会议的开始时间和结束时间" << std::endl;
for (int i = 0; i < all; ++i)
{
std::cin >> data[i].startTime >> data[i].endTime;
data[i].num = i + 1;
}
}
void setMeet::resolve()
{
//对会议进行排序
sort(data, data + all, compare);
std::cout << "排序后的所有数据" << std::endl;
std::cout << "会议的序号" << "\t" << "会议的开始时间" << "\t" << "会议的结束时间" << std::endl;
for (int i = 0; i < all; ++i)
{
std::cout << data[i].num << "\t" << data[i].startTime << "\t" << data[i].endTime << std::endl;
}
//记录排序后的第一次会议结束时间
int lastTime = data[0].endTime;
count = 1;
std::cout << "您选择了第" << data[0].num << "会议" << std::endl;
for (int i = 1; i < all; ++i)
{
/**
if (data[i].startTime < lastTime)
{
continue;
}
else
{
count++;
lastTime = data[i].endTime;
std::cout << "您选择了第" << data[i].num << "会议" << std::endl;
}
**/
//当然我们这样写更好，代码行数减少了，而且看起来没那么别扭
if (data[i].startTime >= lastTime)
{
count++;
lastTime = data[i].endTime;
std::cout << "您选择了第" << data[i].num << "会议" << std::endl;
}
}
std::cout << "一共可以开" << count << "个会议" << std::endl;
}
int main()
{
setMeet meet;
meet.init();
meet.resolve();
return 0;
}4、运行结果
请输入会议的个数
5
您输入的会议个数为5
请输入会议的开始时间和结束时间
1 4
2 6
34
98
4 7
2 9
排序后的所有数据
会议的序号 会议的开始时间 会议的结束时间
1 1 4
2 2 6
4 4 7
5 2 9
3 34 98
您选择了第1会议
您选择了第4会议
您选择了第3会议
一共可以开3个会议5、总结
找到贪心策略是解决问题的关键
全部评论 (0)
还没有任何评论哟~