stall reservations（poj 3190）

贪心解法：

 这里补充一个优先队列priority_queue。附上一篇博客：https://blog.csdn.net/weixin_36888577/article/details/79937886这里面有比较全的优先队列的内容

这个地方用优先队列的时间复杂度低，否则每一次找畜栏的话都要遍历一边所有的畜栏时间复杂度太高了。所以用优先队列，按照结束时间的早晚压入队列中。

#include 
#include 
#include 
#include 
using namespace std;
struct Cow {
    int a, b;
    int No;
    bool operator <(const Cow& c) const {
        return a < c.a;
    }
} cows[50100];
int pos[50100];
struct Stall {
    int end;
    int No;
    bool operator<(const Stall& s)const {
        return end > s.end;
    }
    Stall(int e, int n) :end(e), No(n) { }
};
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> cows[i].a >> cows[i].b;
        cows[i].No = i;
    }
    sort(cows, cows + n);
    int total = 0;
    priority_queue pq;//这个就是优先队列里面的元素是stall
    for (int i = 0; i < n; i++) {
        if (pq.empty()) {
            //如果队列是空的话，就把第一条牛的信息入队
            ++total;
            pq.push(Stall(cows[i].b, total));
            //有点像把牛的信息转成了stall型的结构体
        }
        else {
            Stall st = pq.top();
            //把st放成队头元素
            if (st.end < cows[i].a) {
                //st里面的牛已经好了
                pq.pop();
                //把这个元素pop出来
                pos[cows[i].No] = st.No;
                pq.push(Stall(cows[i].b, st.No));
                //把这个牛给放进去
            }
            else {
                ++total;
                pq.push(Stall(cows[i].b, total));
                pos[cows[i].No] = total;
            }
        }
    }
    cout << total<<endl;
    for (int i = 0; i < n; i++) {
        cout << pos[i] << endl;
    }
}

c++的重载我附上一篇博客：

这里就是用operator操作符把<给重载了，这样sort就会按照struct中重载的规则来排序了。stall中的重载使得queue优先队列按照stall的结束时间排列。这样pop出来的元素就是结束最早的了。