您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

结构体选择活动

题目描述

学校在最近几天有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;
}

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


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进