Poj 2376: Cleaning Shifts

poj2376.md

Poj 2376: Cleaning Shifts

題目

分析

這題是 最少涵蓋區間 。 Greedy 下去就對了。

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval {
    int start, end;

    bool operator<(const Interval& itv) const {
        return start < itv.start;
    }
};

Interval data[25000+1];

int solve(int N, int S) {
    sort(data, data + N);

    int end = 0;
    int cnt = 0;

    int idx = 0;
    for (;;) {
        int new_end = -1;
        while (idx < N && data[idx].start <= end+1) {
            new_end = max(new_end, data[idx].end);
            idx++;
        }
        if (new_end == -1)
            return -1;

        end = new_end;
        cnt++;

        if (idx == N)
            return ((end == S) ? cnt : -1);
        if (end == S)
            return cnt;
    }

    return -1;
}

int main() {
    int N, S;
    scanf("%d %d", &N, &S);

    for (int i = 0; i < N; i++)
        scanf("%d %d", &data[i].start, &data[i].end);
        
    printf("%d\n", solve(N, S));

    return 0;
}