本题本质是贪心法,需要人工设计出最优策略。应用层面上用到了数组排序+PQ的组合,很像502.IPO,但是本题的最优策略要独立思考出来更有难度。
我们尝试按照时间先后顺序来看这些课程.毕竟哪个deadline在前我们就先处理谁,也是非常合情合理的.我们假设在某个课程的deadline之前,手头有一堆的备选课程,我们做其中哪些呢?显然我们做哪些时长要求最少的,从最短的做起,做一个扔掉一个,能做多少做多少,做不完的就扔了,这就是最优的方案了.注意,做不完的不用保留在pool里,因为过了当前的这个deadline之后这些未做的课程就失效了.
假设我们当前已经修了N门.那么接下来又到了下一个deadline,也就是deadline放宽了,但我们又新添了一门课变成N+1门.如果能赶在新deadline之前搞定这门新课,我们自然就是能上就上(那样就是N+1门).如果不能呢?我们自然怪罪当前N+1课程列表里最长的那门,我们只要把那门最长的踢掉就一定满足deadline的要求.(为什么?因为我们之前保证了N门可以满足上一个deadline,那么现在的N门一定也可以满足当前的deadline.)于是,如今虽然同样还是只能修N门,但是踢掉了一个最长的课程,也算是把已修课程列表在时间上给优化了.
于是我们一个接一个的处理deadline,这样得到的就是总的最优方案.