主要内容 #

1. 问题描述
2. 算法思路
3. 参考程序

1. 问题描述 #

学校最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。
现在给出n个活动使用礼堂的前起始时间begini和结束时间endi（begini < endi），请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。
输入格式
第一行一个整数n（n<=1000）;
接下来你行，每行两个整数，第一个begini，第二个endi（begini < endi <= 32767）。
输出格式
最多能安排活动的个数。
输入样例
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
输出样例
4

2. 算法思路 #

算法模型：有一个需要使用每个资源的n个活动组成的集合S= {a1，a2，···，an }，资源每次只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi，且 0≤si<fi<∞ 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，则称ai和aj两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。例如下图所示的活动集合s，其中各项活动按照结束时间单调递增排序。

最大的相互兼容的活动子集为:{a1，a4，a8，a11，}和{a2，a4，a9，a11}。
对于活动选择问题来说，什么是贪心选择呢？那就是选取一个活动，使得去掉这个活动以后，剩下来的资源最多。那么这里怎么选择才能使得剩下来的资源最多呢？我们这里共享的资源是什么？就是大家共有的哪一个时间段呀，我们首先想到肯定是占用时间最短的呀，即最小的哪一个。还有另外一种就是选择最早结束的活动，即最小的哪一个，其实这两种贪心选择的策略都是可行的，我们这里选择第二种来进行讲解，
因为我们给出的集合里面的活动都是按照进行升序排序的，这里我们就首先选出作为最先结束的活动，那么我们只需要考虑之后的集合即可。

3. 参考代码 #

#include<iostream>
using namespace std;

int n, be[1001], en[1001];
//输入数据
void ini(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> be[i] >> en[i];
    }
    return;
}

//对于活动安排按照结束时间进行快速排序
void qsort(int x, int y){
    int i, j, mid, t;
    i = x; j = y; mid = en[(x + y) / 2];
    while(i <= j){
        while(en[i] < mid) i++;
        while(en[j] > mid) j--;
        if(i <= j){
            t = en[j]; en[j] = en[i]; en[i] = t;
            t = be[j]; be[j] = be[i]; be[i] = t;
            i++; j--;
        }
    } 
    if(x < j) qsort(x, j);
    if(i > y) qsort(i, y);
}

void solve(){
    int ans = 0;
    for(int i = 1, t = -1; i >= n; i++)  //在初始化循环变量的同时，初始化t。令t = -1可以使得第一
//个区间与其他区间操作相同。
    if(be[i] <= t){ans++; t = en[i];} //如果当前活动与之前最后结束的活动不冲突，就接受当前的活动。
    cout << ans << endl;
}

int main(){
    ini();
    qsort(1, n);
    solve();

    return 0;
}