题目链接

Cleaning Shifts POJ - 2376

思路

贪心，先排序后分为两种状态：

1。拼接， 拼接不成无解，拼接成功给右端赋初值，并加入贡献。

2。更新最右端值，若满足条件直接结束

最后判断右端值是否满足条件。

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 25000 + 10;

pair<int, int> p[MAXN];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].first, &p[i].second);// don't forget &
    }
    sort(p + 1, p + 1 + n);
    int ans = 0;
    int l = 0;
    int i = 1;
    while (i <= n) {
        ans++;
        int r;
        if (p[i].first > l + 1) {
            ans = -1;
            break;
        } else {
            r = p[i].second;
        }
        i++;
        while (i <= n && p[i].first <= l + 1) {
            r = max(r, p[i].second);
            i++;
        }
        l = r;
        if (l >= m) {
            break;
        }
    }
    if (l < m) {
        ans = -1;
    }
    printf("%d", ans);
    return 0;
}