1372 - 活动选择（C++）

Question

1372 - 活动选择

题目描述

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

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

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

输入

第一行一个整数 n (n≤100)；

接下来的 n 行，每行两个整数，第一个 begin_i ，第二个是 end_i (begin_i< end_i≤ 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

来源

贪心 结构体

标签

https://oj.czos.cn/problem/index?tag=%E8%B4%AA%E5%BF%83https://oj.czos.cn/problem/index?tag=%E7%BB%93%E6%9E%84%E4%BD%93https://oj.czos.cn/problem/index?tag=%E5%8C%BA%E9%97%B4%E9%97%AE%E9%A2%98

代码

#include<bits/stdc++.h>
using namespace std;
/*
要求安排的活动尽量多。请问最多可以安排多少个活动
活动的策略：尽可能选择吧结束时间早的活动
第一步：将结束时间，按照升序排序，开始时间要做联动排序
第二步： 选择第一个活动的结束 时间end为依据，向下找到第一个开始时间>=end的活动为第二个活动，以此类推 
*/
//c：计数器，计算最多能够排几个活动
int b[110],e[110];
int n,i,j,c,end;
int main() {
    cin>>n;
    for(i=1; i<=n; i++) {
        cin>>b[i]>>e[i];
    }
    //对n个活动的起止时间，按照升序进行排序（可以用结构体等）（可以看四大排序，这里用冒泡排序）
    for(i=1; i<=n-1; i++) {
        for(j=1; j<=n-i; j++) {
            if(e[j]>e[j+1]) {
                swap(e[j],e[j+1]);
                swap(b[j],b[j+1]);
            }
        }
    }
    end=e[1];
    c=1;
    for(i=2; i<=n; i++) {
        //找到b[i]>=end的活动，选择它
        if(b[i]>=end) {
            c++;
            end=e[i];
        }
    }
    cout<<c;
    return 0;
}

我的代码是在题目中是编译错误，但是在我的电脑中的DEV-C++中没有编译错误，专家们，看看这个代码，帮帮我吧！

Answer 1

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

struct Activity
{
    int begin;
    int end;
}a[N];

bool cmp(Activity a, Activity b)
{
    return a.end < b.end;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i].begin >> a[i].end;

    // 按照活动的结束时间排序
    sort(a, a + n, cmp);

    int ans = 1; // 初始化答案为1
    int last = a[0].end; // 记录上一个活动的结束时间

    for (int i = 1; i < n; i++)
    {
        // 如果当前活动的开始时间比上一个活动的结束时间晚，则可以安排当前活动
        if (a[i].begin >= last)
        {
            ans++;
            last = a[i].end;
        }
    }

    cout << ans << endl;

    return 0;
}