问题 C: 活动选择

题目描述

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

? ? ? 现在给出n个活动使用礼堂的起始时间bi和结束时间ei(bi < ei<=32767)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

输入

第一行一个整数n(n<=1000)； 接下来的n行，每行两个整数，第一个bi，第二个是ei(bi < ei<=32767)

输出

输出最多能安排的活动个数

样例输入?Copy

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

样例输出?Copy

4

问题分析

我们要想想要怎么贪心，我们的目标是想选到最多的活动

关键是优先选择结束时间最早的活动，这样就为后续的其他活动留下更多的时间

所以我们要先根据每个活动的结束时间从小到大进行排序

第一个活动肯定先被选进来了，然后我们依次看后面的活动和上一个可被选择的活动是否冲突

如果不冲突的话我们就可以选择这个活动，可选择活动数＋1

预备知识

定义结构体，其中Hd是结构体的名字，你可以取自己想取的名字

其中有两个元素，一个bi，一个ei

struct Hd{ //这个结构体的名字叫Hd
    int bi; //存活动开始时间
    int ei; //存活动结束时间
};

cmp是一个自定义的比较函数，用于确定两个Hd结构体实例在排序时的顺序，为sort提供一个排序的准则

接受两个参数，a和b，两个参数都是对Hd结构体的引用，并且是常量引用（由const关键字标示），所以写法是const Hd& a，意味着这些引用在函数内部不会修改它们指向的结构体

bool cmp(const Hd& a,const Hd& b) {
    return a.ei<b.ei; //按活动结束时间从小到大排序
}

每一个元素都是Hd结构体类型，vector就是存多个元素的容器

所以这句话就是有n个Hd类型的元素存在名字叫a的容器当中

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

struct Hd{ //这个结构体的名字叫Hd
    int bi; //存活动开始时间
    int ei; //存活动结束时间
};

bool cmp(const Hd& a,const Hd& b) {
    return a.ei<b.ei; //按活动结束时间从小到大排序
}

int main() {
    int n;
    cin>>n;
    vector<Hd> a(n); //这个vector存的是n个Hd类型的活动，也就是每个元素是个结构体
    for(int i=0;i<n;i++) {
        cin>>a[i].bi>>a[i].ei; //输入每个活动的开始和结束时间
    }
    sort(a.begin(),a.end(),cmp); //对活动进行排序
    int ans=1; //第一个活动被选择
    int end=a[0].ei; //第一个活动的结束时间，以后就是存下一个可选活动结束时间
    for(int i=1;i<n;i++) { //看后续的活动的情况，所以下标是1开始了
        if(a[i].bi>=end) { //如果当前活动的开始时间大于等于前一个可选活动结束时间
            ans=ans+1; //说明该活动与前一个可选活动不冲突，可选活动数加1
            end=a[i].ei; //那么结束时间变为该可选活动结束时间
        }
    }
    cout<<ans; //输出几个可安排的活动
}