#include<iostream>
#include<string>
#include<memory.h>
#include<cstdio>
#include<string>
#include <algorithm>
#define NUM 1000
using namespace std;
int charaNum[NUM] ;//存放输入数据的数组
int tempArr[NUM];
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;
}
action a[NUM];
int GreedySelect(int n,action a[])
{
int sum = 1;
cout<<a[1].index<<" ";
int perEnd = 1;
for(int i = 2;i<=n;i++)
{
if(a[perEnd].f<=a[i].s)
{
sum++;
perEnd = i;
cout<<a[i].index<<" ";
}
}
cout<<endl;
return sum;
}
int main()
{
freopen("in.txt","r",stdin);
int num;
while (cin>>num && num != 0)
{
for(int i = 0;i<num;i++)
{
cin>>a[i+1].s>>a[i+1].f;
a[i].index = i+1;
}
sort(a,a+num+1,cmp);
cout<<GreedySelect(num,a)<<endl;
}
}
输入：
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
输出：
2 3 11 8 6 5
转载请注明原文地址: https://ju.6miu.com/read-673057.html
