《算法竞赛进阶指南》Stall Reservations题解

思路：

本题用了贪心+优先队列，本题要用尽量少的摊位让更多的奶牛生产，所以尽量能够让一个结束后，另一个能够接上，所以先排序将开始时间早的排前面，然后开始用优先队列，把结束时间早的排在前面，（把最早开始时间的放在前面，最早结束时间放在前面，如果这都接不上，那么肯定要开个摊位了），如果能接上的话，就将最早结束时间刷新，也就是说，这个摊位的最早结束时间变成了接上的那个奶牛的结束时间，需要注意的是加入1 4 和4 7必须要两个摊位，因为在4这个时间点，是两个奶牛都要在摊位里面，题目不允许，本题的摊位会发生没有奶牛生产，所以无需考虑队列为空这种情况。

优先队列：

优先队列是用堆实现的，但是用法上相当于队列+排序，队列里的元素你可以设置成从小到大或者从大到小，无论是加入元素还是删除元素优先队列始终保持有序。

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct NODE {
    int start;
    int end;
    int stall;
    int id;
    friend bool operator < (NODE a, NODE b) {
        return a.end > b.end;
    }
};
NODE node[50010];
bool cmp(NODE a, NODE b) {
    return a.start < b.start;
}
bool cmp2(NODE a, NODE b) {
    return a.id < b.id;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> node[i].start >> node[i].end;
        node[i].id = i;
    } 
    sort (node, node + n, cmp);
    priority_queue<NODE> q;
    int num = 1;
    node[0].stall = num;
    q.push(node[0]);
    for (int i = 1; i < n; i++) {
        if (node[i].start > q.top().end) {
            node[i].stall = q.top().stall;
            q.pop();
            q.push(node[i]);
        } else {
            node[i].stall = ++num; 
            q.push(node[i]);
        }
    }
    cout << num << endl;
    sort(node, node + n, cmp2);
    for (int i = 0; i < n; i++) {
        cout << node[i].stall << endl;
    } 
    return 0;
}