51nod贪心算法入门-----活动安排问题

发表于 | 分类于 |

有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？

输入

第1行：1个数N，线段的数量(2 <= N <= 10000)
第2 - N + 1行：每行2个数，线段的起点和终点(-10^9 <= S,E <= 10^9)
输出

输出最多可以选择的线段数量。

输入示例

3
1 5
2 3
3 6

输出示例

2

我们可以知道先安排最早结束的活动可以更多的安排活动。首先就是将所有的活动结束时间按先后顺序给排序；然后以结束时间为线索一路检索下去，判断开始时间是否早于前面一次活动的结束时间。这里可以用结构体或者两个数组来把一个活动的开始时间和结束时间联系起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
#include<iostream>
#define max 10001
using namespace std;
int main(){
    int n,i,j,temps,tempo;
    int start[max],over[max];
    while(scanf("%d",&n)!=EOF){
            int sum=0,t=-1000000000;
    for(i=0;i<n;i++){
        cin>>start[i]>>over[i];
    }
    for(i=0;i<n;i++)
       for(j=i;j<n;j++){
           if(over[i]>over[j]){
              tempo=over[i];
              over[i]=over[j];
              over[j]=tempo;
              temps=start[i];
              start[i]=start[j];
              start[j]=temps;
           }
       }
    for(i=0;i<n;i++){
        if(t<=start[i]){
            t=over[i];
            sum+=1;
        }
    }
    printf("%d\n",sum);
    }
    return 0;
}

//原本我还考虑了活动时间不能为负数的情况，但是在提交时系统给出的数据中把负数也给算了进去。。。。。