题目链接

算法竞赛进阶指南-25.畜栏预定

本题是一道区间问题，区间问题往往具有贪心策略，并与排序相关。

Method : 贪心

区间分组问题， 分组组数==最大区间厚度

启发式策略：

1. 区间按左端点升序排序

2. 顺序枚举，分类讨论

   • 如果之前存在一个组的区间右端点不与当前区间左端点相交，则将当前区间插入该组，并更新该组的右端点
   • 如果之前不存在一个组的区间右端点不与当前区间左端点相交，则将当前区间插入该组

   区间的组可以用小根堆(组的区间右端点)维护，每次取出堆顶与当前区间进行判断。

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e4 + 7;

struct Node {
    int l;
    int r;
    int id;
    bool operator < (const Node & rhs) const {
        if (l == rhs.l) return r < rhs.r;
        else return l < rhs.l;
    }
};

vector<Node> cows;
vector<int> id;

auto cmp = [](const Node &a, const Node &b) -> bool{
    return a.r > b.r;
};
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

int n;

int main() {
    cin >> n;
    id.resize(n);
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        cows.push_back({l, r, i});
    }

    sort(cows.begin(), cows.end());

    for (int i = 0; i < n; i ++) {
        // 可以往后拼接
        if (!pq.empty() && pq.top().r < cows[i].l) {
            auto t = pq.top(); pq.pop();
            t.r = cows[i]. r;
            id[cows[i].id] = t.id;
            pq.push(t);
        }
        // 新开一个畜栏
        else {
            id[cows[i].id] = pq.size() + 1;
            pq.push({cows[i].l, cows[i].r, pq.size() + 1});
        }
    }

    cout << pq.size() << endl;
    for (int i = 0; i < n; i ++) printf("%d\n", id[i]);

    return 0;
}

复杂度分析

• 时间复杂度${O(nlogn)}$， 其中$nlogn$为调整优先队列的时间复杂度。

• 空间复杂度${O(n)}$。