活动选择

深藏阁楼爱情的钟 2023-06-13 11:13 40阅读 0赞

欢迎访问我的个人博客：[苦酒的个人小站][Link 1]

# 题目描述 #

Problem Description  
学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划（即活动的开始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。  
比如有5个活动，开始与截止时刻分别为：

![format_png][]

最佳安排序列为：1,4,5。

Input

第一行输入活动数目ｎ（0<ｎ<100）；

以后输入ｎ行，分别输入序号为1到ｎ的活动使用中心的开始时刻ａ与截止时刻ｂ（a,b为整数且0<=a,b<24，a,b输入以空格分隔）。

Output

输出最佳安排序列所包含的各个活动（按照活动被安排的次序，两个活动之间用逗号分隔）。

Sample Input

6  
8 10  
9 16  
11 16  
14 15  
10 14  
7 11

Sample Output

1,5,4

# 题目思路 #

刚看到这道题，还是有点懵逼的。  
总结一下题目的大致意思：**给你N个活动，每个活动有对应的开始和结束以及编号，让你找一个最合适的方法，来使进行的活动最多。**  
直接开一个结构体，里面包含每个活动的开始、结束、编号、时间区间，这里的时间区间主要是为了后面排序使用，对于结构体进行排序，依次遍历，输出结果。

# 题目代码 #

#include <iostream>
    #include <algorithm>
    #include <stdio.h>
    using namespace std;
    
    struct node
    {
        int start;//定义每一个的开始时间
        int finish;//定义每一个的结束时间
        int id;//为每一个活动赋予其相应的id
        int section;//定义每一个活动的区间范围，也就是执行活动的时间大小
    } st[1222];
    
    int cmp(node a, node b)
    {
        if(a.finish == b.finish)
        {
            return a.section < b.section;//如果结束时间相同的话，则根据区间的大小进行排序。
        }
        else
        {
            return a.finish < b.finish;//根据结束时间进行升序排序
        }
    }
    int main()
    {
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++)
        {
            cin>>st[i].start>>st[i].finish;
            st[i].id = i;
            st[i].section = st[i].finish - st[i].start;
        }
        sort(st + 1,st + n + 1,cmp);//对当前的结构体按照结束的时间进行排序，如果结束的时间相等的话，则根据区间排序。
        printf("%d", st[1].id);//排序完之后，选取第一个肯定是最优的。
        int x = st[1].finish;
        for(int i = 2; i <= n; i++)
        {
            if(st[i].start >= x)
            {
                printf(",%d", st[i].id);
                x = st[i].finish;
            }
        }
        printf("\n");
        return 0;
    }
    
    
    /***************************************************
    User name: jk170631黄良帅
    Result: Accepted
    Take time: 0ms
    Take Memory: 200KB
    Submit time: 2019-11-16 17:04:54
    ****************************************************/

[Link 1]: https://www.huangliangshuai.com/2019/11/16/%E7%AE%97%E6%B3%95/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/%E6%B4%BB%E5%8A%A8%E9%80%89%E6%8B%A9/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hY20uc2R1dC5lZHUuY24vaW1hZ2UvMTI5OC5wbmc?x-oss-process=image/format,png