1. 题目

传送门= ̄ω ̄=

2. 题解

考虑倒推。
设$f(i)$为时刻$i$到时刻$n$之间的最大空暇时间。
如果时刻$i$无任务开始,显然$f(i)=f(i+1)+1$。
否则枚举开始于时刻$i$的任务,设当前枚举的任务结束时间为$j$,则$f(i)=max(f(j+1))$。
至于保存每个时刻有哪些任务开始,用链表(或者模拟,即链式前向星)即可。

还有一点要注意的,一个任务开始与$a$,持续时间为$b$,那么它的结束时间不是$a+b$而是$a+b-1$。
下面的代码中我直接用$a+b$表示任务结束时间,这样在算$f(i)=max(f(j+1))$时就不用加一了。

代码: