把气球抽象成 $n$ 个任务：每个任务需要花 $D_i$ 的时间完成，需要在 $L_i$ 时间之前开始——换句话说，需要在 $L_i+D_i$ 时间前完成，相当于是个 DDL。问题转化成求最多有多少个任务能赶在 DDL 前完成。

重置一下记号，记完成所需要的时间为 $a_i:=D_i$，DDL 为 $d_i:=L_i+D_i$。将所有任务按 $d_i$ 升序排序，维护前 $i$ 个任务的最优安排方案。

用大根堆记录它们的 $a$ 以及 $\sum a$。考虑第 $i$ 个任务时先将 $a_i$ 加入堆，若 $\sum a\leq d_i$ 则将其计入答案，若 $\sum a > d_i$ 就从堆中选出 $a$ 最大的元素删去，这样就能实现答案最大化。时间复杂度 $\mathcal{O}(n\log n)$。

事实上，上面策略的证明不太美丽。思路大概分两步走：（1）按照截止时间排序一定是最优的；（2）丢掉运行时间最长的任务是最优的；具体证明过程如下。

引理 1. 若按 $d_i$ 排序后有一个任务无法完成，则至少有一个任务无法完成。

证明. 第一个无法完成的任务 $k$ 满足 $\sum_{i\in[k]} a_i > d_{k}$，假设有一种最优安排使得前 $k$ 个任务都可以完成并且前 $k$ 个任务中最后一个做的是 $j$，那么它的结束的时间至少为 $\sum_{i\in[k]} a_i > d_{j}$，矛盾。$\Box$

引理 2. 在排序策略下，若第一个无法完成的任务 $k$ 将堆里弹出的任务是 $m$，则一定存在一个最优安排使得 $m$ 被拒绝。

证明. 对任意一组最优安排，令其接受集合为 $S$，拒绝集合为 $R:=[n]\,\backslash\,S$。如果 $m\notin R$，就会存在 $r\in [k]$ 使得 $r\in R$。

构造另一组安排 $S^\prime = (S\,\backslash\,m)\cup r$，根据引理 1，$S$ 和 $S^\prime$ 的任务都可以按照排序策略执行并且可以让 $S$ 和 $S^\prime$ 中前 $k-1$ 个任务完成。$S^\prime$ 中 $k$ 结束的时间满足 $\sum_{i\in [k]\,\backslash\,m} a_i \leq \sum_{i\in [k-1]} a_i \leq d_{k-1}\leq d_k$，合法。

而由于 $a_{r}\leq a_{m}$ 使得 $S^\prime\,\backslash\,[k]$ 开始的时间一定早于 $S\,\backslash\,[k]$，一定不劣。因此 $S^\prime$ 是一组最优安排。$\Box$

定理 3. 上述算法的构造是一组最优安排。

证明. 对最少无法完成的任务数 $\textsf{REJ}(I)$ 使用归纳法。

若 $\textsf{REJ}(I)=0$，由引理 1 排序策略一定能完成所有任务，符合条件。

若 $\textsf{REJ}(I)\geq 1$，设第一个被弹出的任务是 $m$ 并令 $I^- = I\,\backslash\,m$，根据引理 2 有 $\textsf{REJ}(I^-) = \textsf{REJ}(I) -1$。

上述算法给出的最优安排满足 $S^{-}=S$ 且 $R=R^{-}\cup m$，故 $|R|=\textsf{REJ}(I)$。上述算法可以给出当前的最优安排，根据归纳法可知对所有集合成立。$\Box$