题目描述

学校在最近几天有n（n<=100）个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出n个活动使用礼堂的起始时间begini和结束时间endi(begini < endi)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。请问最多可以安排多少活动？

请注意，开始时间和结束时间均指的是某个小时的0分0秒，如：3 5，指的是3:00~5:00，因此3 5和5 9这两个时间段不算冲突的时间段。

输入

第一行一个整数n(n<=100)

接下来的n行，每行两个整数，第一个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

代码实现

#include <bits/stdc++.h>
using namespace std;

struct Time {
    int b, e;

} a[110];
//因为是结构体，所以输入的自然也是结构体了
bool cmp(Time s1, Time s2) {
    if (s1.e < s2.e) {
        return true;
    } else {
        return false;
    }
}

int main() {
    int n, c = 0, k;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].b >> a[i].e;
    }
    //sort的用法大家都很熟把
    sort(a, a + n, cmp);
    //排序后第一个活动必选
    c = 1;
    k = a[0].e;//k存结束的时间
    //遍历剩余的活动
    for (int i = 0; i < n; i++) {
        if (a[i].b >= k) {
            c++;
            k = a[i].e;//记得改变k的值
        }
    }
    cout << c;
    return 0;
}

//这题中使用结构体就非常简单了，这就把开始和结束的时间捆绑在了一起，这就方便我们去遍历了。