活动安排问题,贪心算法
作者:
嘉诺
,
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;
return false;
}
void tanxin(int n, action a[], bool b[])
{
b[1] = true;
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)
{
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;
}