活动安排问题,贪心算法
作者:
嘉诺
,
2020-11-16 09:25:25
,
所有人可见
,
阅读 753
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
struct action{
int s; //起始时间
int f; //结束时间
int index; //编号
};
bool cmp(const action &a, const action &b)
{
if (a.f<=b.f) return true; //如果a项目的结束时间晚于b项目,返回true
return false;
}
void tanxin(int n, action a[], bool b[])
{
b[1] = true; //第一个活动必选
//记录最近一次加入到集合b中的活动
int preEnd = 1;
for(int i=2; i<=n; i++)
if (a[i].s>=a[preEnd].f)
{
b[i] = true;
preEnd = i;
}
}
int main()
{
int n;
while(cin>>n && n) //当n存在时
{
action a[1000]; //记录活动的开始时间,结束时间及编号
bool b[1000]; //记录每一个活动选不选
memset(b,false,sizeof(b)); //一开始活动全部不选
for(int i=1; i<=n; i++)
{
cin>>a[i].s>>a[i].f;
a[i].index = i;
}
sort(a, a+n+1, cmp); //将所有活动从前往后进行排序
tanxin(n, a, b); //调用贪心算法
for(int i=1; i<=n;i++)
if(b[i]) cout<<a[i].index<<" ";
cout<<endl;
}
return 0;
}