题意 > nnn天，mmm个租借订单，第iii天有rir_iri 个教室可用,对于一条租借订单dj,sj,tjd_j,s_j,t_jdj ,sj ,tj ,代表从天sjs_jsj 到天tjt_jtj 都需要djd_jdj 个教室，问是否可以满足所有订单，若不满足返回第一个不满足的订单编号 暴力 首先很容易想到用前缀和与差分实现的暴力方法，每次修改差分，再求前缀和判断，这样的算法是O(n×m)O(n\times m)O(n×m) 优化 我们希望能压缩到O(n log(m))O(n\ log(m))O(n log(m))或者O(m log(n))O(m\ log(n))O(m log(n))的复杂度，考虑优化找到需要修改订单这一部分 我们假设对于第xxx个订单之前的每个订单都实现 易知性质：若到第xxx个订单没超限，则必有前x−1x-1x−1个订单都满足 所以判断一个订单能否被满足，只用修改前xxx次的差分后求前缀和即可，这个很简单 与此同时我们发现这个性质也是单调性的一种，如果第xxx个是满足的那么前面的第111到xxx区间的都肯定满足，不满足的订单一定出现在第x+1x+1x+1到nnn区间里或者是不存在；同理如果第xxx不满足，其余更优的不满足的订单一定在第111到xxx区间或者不存在 因此我们可以考虑使用二分，二分每一个订单 若这个订单可以满足，往右边继续查找订单即可，遇到不满足的时候保存答案，往左边查找 得到O(n log(m))O(n\ log(m))O(n log(m))的算法 代码