UVALive 2326 Moving Tables 貪心

題意：你有幾個搬東西的任務，從一間教室到另一間需要10分鐘，但是在此期間，你需要經過的走廊不能又其他任務占用，求最短時間。 教室分布如下：   很明顯的貪心，其實就是找出最少有幾個不相交區間就可以了，循環找出來，復雜度為O(n^2)，這樣是可行的，因為數據量不是很大，只到200。 但是如果數據量大點就會超時了，於是我想了個o(nlogn+n)的辦法，排序後遍歷一遍，拿個數組記錄每一組不相交區間的最末尾的值，每次查詢能不能放到某組區間裡面，能就放進去，不能就再開辟一個數組。 比較坑的是輸入的兩個房間不一定是左邊大於右邊，在這裡wa了一次。 代碼：  

 /* 
 *   Author:        illuz <iilluzen[at]gmail.com> 
 *   Blog:          http://blog.csdn.net/hcbbt 
 *   File:          uvalive2326.cpp 
 *   Lauguage:      C/C++ 
 *   Create Date:   2013-09-07 14:19:24 
 *   Descripton:    UVALive 2326 Moving Tables, greedy  
 */  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define rep(i, n) for (int i = 0; i < (n); i++)  
#define mc(a) memset(a, 0, sizeof(a))  
  
const int MAXN = 210;  
struct P {  
    int lhs, rhs;  
} p[MAXN];  
int t, n, vis[MAXN], rec[MAXN], a, b;  
  
bool cmp(P a, P b) {  
    return a.lhs < b.lhs;  
}  
  
int main() {  
    scanf("%d", &t);  
    while (t--) {  
        scanf("%d", &n);  
        if (n == 0) {  
            printf("0\n");  
            continue;  
        }  
        rep(i, n) {  
            scanf("%d%d", &a, &b);  
            a = (a + 1) / 2;  
            b = (b + 1) / 2;  
            if (a == b) i--, n--;  
            else {  
                p[i].lhs = min(a, b);  
                p[i].rhs = max(a, b);  
            }  
        }  
        sort(p, p + n, cmp);  
        int ans = 0;  
        mc(vis); mc(rec);  
        for (int i = 0; i < n; i++) {  
            if (vis[i] == 0) {  
                vis[i]++;  
                int ok = false;  
                for (int j = 1; j <= ans && !ok; j++)  
                    if (rec[j] < p[i].lhs)  
                        rec[j] = p[i].rhs, ok = true;  
                if (!ok)  
                    rec[++ans] = p[i].rhs;  
            }  
        }  
        if (ans == 0) printf("10\n");  
        else printf("%d\n", ans * 10);  
    }  
    return 0;   
}