题目描述

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
****************************************************/