AcWing 111. 畜栏预定

题目链接：111. 畜栏预定 - AcWing题库

按照开始吃草的时间把牛排序。

维护一个数组 $S$，记录当前每个畜栏安排进去的最后一头牛，最初没有畜栏。

依次对于每头牛，扫描数组 $S$，找到任意一个畜栏，满足当前的牛开始吃草的时间不早于畜栏中最后一头牛结束吃草的时间。

如果这样的畜栏不存在，则为其新建一个畜栏。

这个贪心算法的时间复杂度是 $\mathcal{O}(N^2)$，请读者自行证明其正确性。

我们可以用一个小根堆（STL priority_queue）维护每个畜栏最后一头牛结束吃草的时间，尝试把当前的牛安排在堆顶（结束时间最早）的畜栏中，时间复杂度可以降低到 $\mathcal{O}(N \log(N))$。

完整代码：畜栏预定.cpp