zrt4

· · 个人记录

贪心是显然的，按照右端点排序，同时维护一个堆存放每间教室的最后一场活动结束时间。每次看能不能放进去，能放就尽量放。这个贪心是经典的。

只有所有的教室都占用了，我们才会开新教室用。因此，我们可以二分出来 mn_i，表示 i 一定会用的最少教室数量。显然算出 mn 我们就做完了。

单次二分的过程，是我们模拟这个贪心过程，看看这个位置会不会选到。考虑整体二分。

整体二分到值域区间 [L, R] 区间时，我们要看哪些点的 mn 小于等于 mid。可以通过线段树区间加，看区间最大值是否小于 mid。

好牛逼的题