\(N\) (\(1 \le N \le 25,000\))只蛤,每只蛤只能在特定时间段工作。 \(T\) (\(1 \le T \le 1,000,000\))个时间段。 找到最少蛤数能覆盖整个时间段。

链接:http://poj.org/problem?id=2376

助攻

  • 每个时间段都至少要有一只蛤。
  • 每只蛤在结束时间之后结束。比如说有两只蛤工作时间段分别是\((1, 3)\)和\((4, 10)\)。这样被认为时间段是连续的,在\(T = 10\)的时候是可行的。
  • 任何时间段之间不能断。
  • scanf()作为输入不然超时。






题解

按结束时间排序。对每个区间谈心,找到每只在当前时间段内开始,结束最晚的蛤。因为已经排过序啦,所以只要判断开始时间是不是比当前的时间小,第一个找到的就是了。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;


vector<P> v;
int N, T, ans = 0;

struct cmp {
    bool operator()(const P &l, const P &r) {
        return l.second > r.second;
    }
};
void solve() {
    sort(v.begin(), v.end(),cmp());
    int cur = 1;
    bool find = true;
    while (cur <= T) {
        if ((v.size() == 0) || !find || (v[0].second < cur)) { ans = -1; return ; }
        for (int i = 0; i < v.size(); i++) {
            if (v[i].first <= cur) {
                ans++;
                cur = v[i].second+1;
                printf("%d %d\n\n", v[i].first, v[i].second);
                v.erase(v.begin()+i);
                find = true;
                break;
            }
            find = false;
        }
    }
    return ;
}

int main(void) {
    scanf("%d %d", &N, &T);
    int start, end;
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &start, &end);
        v.push_back(P(start, end));
    }

    solve();
    printf("%d\n", ans);

    return 0;
}