活动选择

题目描述

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

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

Input

第一行输入活动数目n(0<n<100);

以后输入n行,分别输入序号为1到n的活动使用中心的开始时刻a与截止时刻b(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个活动,每个活动有对应的开始和结束以及编号,让你找一个最合适的方法,来使进行的活动最多。
直接开一个结构体,里面包含每个活动的开始、结束、编号、时间区间,这里的时间区间主要是为了后面排序使用,对于结构体进行排序,依次遍历,输出结果。

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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
****************************************************/
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信