问题 C: 活动选择

2024-01-07 22:05:39
题目描述

? ? ? 学校在最近几天有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; //输出几个可安排的活动
}

文章来源:https://blog.csdn.net/lcc1737/article/details/135421849
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。