UVA - 1420 Priest John's Busiest Day

UVA - 1420 Priest John's Busiest Day

題目大意：有一個司儀，要主持 n 場婚禮，給出婚禮的起始時間和終止時間，每個婚禮需要超過一半的時間做為儀式，並且儀式不能終止。問說司儀能否主持 n 場婚禮。

解題思路：貪心，為了盡量主持多的婚禮，每場的儀式時間就一定要盡量短 d = (t - s) / 2 + 1,(因為必須大於一半，所以加 1）。然後按照每場婚禮可以最晚結束的時間排序 t - d，（因為要滿足所有的婚禮，所以盡量解決早點的儀式，騰出時間來給後面的婚禮），維護一個占用時間值即可。

#include 
#include 
using namespace std;

struct Wedding {
    int S, T, D;
    bool operator < (const Wedding& a) const {
        return T - D < a.T - a.D;
    }
} W[100010];

bool judge(int N) {
    int cur = 0;
    for (int i = 0; i < N; i++) {
        cur = max(cur, W[i].S) + W[i].D;
        if (cur > W[i].T)
            return false;
    }
    return true;
}

int main() {
    int N;
    while (scanf(%d, &N) && N) {
        for (int i = 0; i < N; i++) {
            scanf(%d%d, &W[i].S, &W[i].T);
            W[i].D = (W[i].T - W[i].S) / 2 + 1;
        }
        sort(W, W + N);

        printf(%s
, judge(N) ? YES : NO);
    }
    return 0;
}