最近希望在日常加强一下算法的水平，所以找了一个ACM网站来强行刷水题，不过脑子笨，刷个题老半天的，果然技术有限啊，先做个最简单的会场安排问题来增强一下自信心吧。
描述
学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
输入
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)
输出
对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始
我们直接来考虑算法部分的问题吧，如果从一组活动数据中算出会场安排的最优解，我们需要好好的分析问题，抽取问题的实质才行。比如这个会场安排问题，怎么才能矩形尽可能多的活动呢？自然是活动的时间尽可能短，并且不同的活动能够进行衔接，那么举办的活动数量就最多的了。比如下面的
活动安排
首先能够衔接的会议必定是下一个活动的开始时间必定是大于上一个活动的结束时间，而下一个活动的结束时间必定是大于上一个活动的结束时间的，如果存在两个活动互斥，但是都能够跟下一个活动衔接，那么我们就不需要考虑这些互斥的活动了，可以把这些互斥的活动算作一个单位。
假如存在一个更小的活动，可以跟这些互斥的活动中的一个或两个衔接，那么这个更小的活动的结束时间必然都小于互斥活动的开始时间和结束时间，又因为这些活动的数据输入时是无序的，所以首先要做的就是对所有活动进行排序。
private static int meeting_problem(int[] startTime,int[] endTime){
//一组活动数据的最优解
int maxresult = 1;
//冒泡排序，对startTime和endTime数据进行排序
for (int i = 0; i < endTime.length-1; i++) {
boolean canBreak = 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;
canBreak = false;
}
}
if (canBreak) {
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;
}
上面就是获取一组活动数据的最优解，结合输入数据的代码
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] = (meeting_problem(startTimes, endTimes));
}
for (Integer result:results) {
System.out.println(result);
}
}
最后当然是通过了ACM的编译了，可是发现了一个很严肃的问题，我不清楚是我的实现上有问题，还是Java和C++之间有这么大的效率差距
所以说刷水题还是用C/C++好一点，顺道把C++捡回来也好，毕竟C++可以做Cocos-2d，而且安卓底层也需要用到c的基础，总是好处很多的。
非常的尴尬，本来想用C++实现一次的，但是自己跑的时候能跑通，放上ACM就出错了，不知道哪里出了问题。。。
#include<iostream>
#include <algorithm>
using namespace std;
struct active
{
int begin;
int end;
};
bool cmp(active x,active y)
{
return x.end<y.end;
}
int schedule(active* actives,int s,int e)
{
int n=0;
int i=s+1;
if (actives[s].begin > -1){
n=1;
for(;i<=e;i++)
if(actives[i].begin- actives[s].end >= 1){
s=i;
n++;
}
}
return n;
}
int main( )
{
int n,group;
cin>>n;
int *result = new int[n];
for(int j=0;j<n;j++){
cin>>group;
active *st= new active[group];
for(int i=0;i<group;i++)
cin>>st[i].begin>>st[i].end;
sort(st,st+group,cmp);
result[j] = schedule(st,0,group-1);
delete []st;
}
for(int i= 0;i<n;i++)
cout<< result[i] <<endl;
delete []result;
return 0;
}
或者使用C++效率更高也未可知吧。。。好久不用的C++捡回来也是够呛
网友评论