最近希望在日常加強(qiáng)一下算法的水平，所以找了一個(gè)ACM網(wǎng)站來(lái)強(qiáng)行刷水題，不過(guò)腦子笨，刷個(gè)題老半天的，果然技術(shù)有限啊，先做個(gè)最簡(jiǎn)單的會(huì)場(chǎng)安排問(wèn)題來(lái)增強(qiáng)一下自信心吧。

描述
學(xué)校的小禮堂每天都會(huì)有許多活動(dòng)，有時(shí)間這些活動(dòng)的計(jì)劃時(shí)間會(huì)發(fā)生沖突，需要選擇出一些活動(dòng)進(jìn)行舉辦。小劉的工作就是安排學(xué)校小禮堂的活動(dòng)，每個(gè)時(shí)間最多安排一個(gè)活動(dòng)?，F(xiàn)在小劉有一些活動(dòng)計(jì)劃的時(shí)間表，他想盡可能的安排更多的活動(dòng)，請(qǐng)問(wèn)他該如何安排。

輸入
第一行是一個(gè)整型數(shù)m(m<100)表示共有m組測(cè)試數(shù)據(jù)。
每組測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)n(1<n<10000)表示該測(cè)試數(shù)據(jù)共有n個(gè)活動(dòng)。
隨后的n行，每行有兩個(gè)正整數(shù)Bi,Ei(0<=Bi,Ei<10000),分別表示第i個(gè)活動(dòng)的起始與結(jié)束時(shí)間（Bi<=Ei)
輸出
對(duì)于每一組輸入，輸出最多能夠安排的活動(dòng)數(shù)量。
每組的輸出占一行

注意：如果上一個(gè)活動(dòng)在t時(shí)間結(jié)束，下一個(gè)活動(dòng)最早應(yīng)該在t+1時(shí)間開(kāi)始

我們直接來(lái)考慮算法部分的問(wèn)題吧，如果從一組活動(dòng)數(shù)據(jù)中算出會(huì)場(chǎng)安排的最優(yōu)解，我們需要好好的分析問(wèn)題，抽取問(wèn)題的實(shí)質(zhì)才行。比如這個(gè)會(huì)場(chǎng)安排問(wèn)題，怎么才能矩形盡可能多的活動(dòng)呢？自然是活動(dòng)的時(shí)間盡可能短，并且不同的活動(dòng)能夠進(jìn)行銜接，那么舉辦的活動(dòng)數(shù)量就最多的了。比如下面的

活動(dòng)安排

首先能夠銜接的會(huì)議必定是下一個(gè)活動(dòng)的開(kāi)始時(shí)間必定是大于上一個(gè)活動(dòng)的結(jié)束時(shí)間，而下一個(gè)活動(dòng)的結(jié)束時(shí)間必定是大于上一個(gè)活動(dòng)的結(jié)束時(shí)間的，如果存在兩個(gè)活動(dòng)互斥，但是都能夠跟下一個(gè)活動(dòng)銜接，那么我們就不需要考慮這些互斥的活動(dòng)了，可以把這些互斥的活動(dòng)算作一個(gè)單位。
假如存在一個(gè)更小的活動(dòng)，可以跟這些互斥的活動(dòng)中的一個(gè)或兩個(gè)銜接，那么這個(gè)更小的活動(dòng)的結(jié)束時(shí)間必然都小于互斥活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間，又因?yàn)檫@些活動(dòng)的數(shù)據(jù)輸入時(shí)是無(wú)序的，所以首先要做的就是對(duì)所有活動(dòng)進(jìn)行排序。

    private static int meeting_problem(int[] startTime,int[] endTime){
        //一組活動(dòng)數(shù)據(jù)的最優(yōu)解
        int maxresult = 1;
         //冒泡排序，對(duì)startTime和endTime數(shù)據(jù)進(jìn)行排序
        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;
            }
        }
        // 記錄上一次活動(dòng)的結(jié)束時(shí)間
        int key = endTime[0];
        for (int i = 1; i < endTime.length; i++) {
            // 如果活動(dòng)的開(kāi)始時(shí)間能夠大于上一次活動(dòng)的結(jié)束時(shí)間
            if (startTime[i] - key >= 1){
                //計(jì)數(shù)+1
                maxresult ++;
                //保存結(jié)束時(shí)間
                key = endTime[i];
            }
        }
        return maxresult;
    }

上面就是獲取一組活動(dòng)數(shù)據(jù)的最優(yōu)解，結(jié)合輸入數(shù)據(jù)的代碼

    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);
        }
    }

最后當(dāng)然是通過(guò)了ACM的編譯了，可是發(fā)現(xiàn)了一個(gè)很?chē)?yán)肅的問(wèn)題，我不清楚是我的實(shí)現(xiàn)上有問(wèn)題，還是Java和C++之間有這么大的效率差距

所以說(shuō)刷水題還是用C/C++好一點(diǎn)，順道把C++撿回來(lái)也好，畢竟C++可以做Cocos-2d，而且安卓底層也需要用到c的基礎(chǔ)，總是好處很多的。
非常的尷尬，本來(lái)想用C++實(shí)現(xiàn)一次的，但是自己跑的時(shí)候能跑通，放上ACM就出錯(cuò)了，不知道哪里出了問(wèn)題。。。

#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++撿回來(lái)也是夠嗆