算法打卡40：会场安排问题
365算法每日学计划
40打卡：
- 描述
- 学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
- 输入
- 第一行是一个整型数m(m<100)表示共有m组测试数据。 每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。 随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei) </n<10000)表示该测试数据共有n个活动。
- 输出
- 对于每一组输入，输出最多能够安排的活动数量。 每组的输出占一行
- 样例输入
- 2 2 1 10 10 11 3 1 10 10 11 11 20
- 样例输出
- 1 2
思路：
贪心思想解决。
其实，就是求尽可能多的不相交的区间。将时间区间按照结束时间升序排列，如果结束时间相同，按开始时间降序排列。
具体来说，对开始时间和结束时间进行排序，如果活动的开始时间能够大于上一次活动的结束时间，活动的数量就+1.
import java.util.Scanner;
public class _40 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int[] results = new int[num];
for (int i = 0; i < num; i++) {
int a = scanner.nextInt();
int[] startTimes = new int[a];
int[] endTimes = new int[a];
for (int j = 0; j < a; j++) {
startTimes[j] = scanner.nextInt();
endTimes[j] = scanner.nextInt();
}
results[i] = solve(startTimes, endTimes);
}
for (Integer result : results) {
System.out.println(result);
}
}
private static int solve(int[] startTime, int[] endTime) {
int maxresult = 1;
//冒泡排序，对startTime和endTime数据进行排序
for (int i = 0; i < endTime.length - 1; i++) {
boolean flag = true;
for (int j = 1; j < endTime.length - i; j++) {
if (endTime[j - 1] > endTime[j]) {
int temp = endTime[j - 1];
endTime[j - 1] = endTime[j];
endTime[j] = temp;
int temp2 = startTime[j - 1];
startTime[j - 1] = startTime[j];
startTime[j] = temp2;
flag = false;
}
}
if (flag) {
break;
}
}
// 记录上一次活动的结束时间
int key = endTime[0];
for (int i = 1; i < endTime.length; i++) {
// 如果活动的开始时间能够大于上一次活动的结束时间
if (startTime[i] - key >= 1) {
//计数+1
maxresult++;
//保存结束时间
key = endTime[i];
}
}
return maxresult;
}
}
觉得有用就转发分享一下吧
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-08-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读