ABC131 D - Megalomania - ツバサの備忘録

解法

やることから先に言うと、
$A_{i},B_{i}$ を $B_{i}$ の昇順でソートし、 $1 \leqq k \leqq N$ を満たす任意の $k$ について、
$\displaystyle \sum_{i=1}^{k}A_{i} \leqq B_{i}$
が成立すれば答えがYesになり、1つでもこれが成立しなければNoになります。
結局、時刻 $B_{i}$ の時点では、締め切りが $B_{i}$ 以下の仕事については全て終えている必要があるので、それらにかかる時間の総和が $B_{i}$ を超えているかどうかを調べればよいです。

感想

区間スケジューリングの典型的な問題をすこしひねったような問題に見えました。
区間スケジューリングが区間の後ろでソートしてうまく貪欲をしていくものだったことを考えると、この問題の方針が見えました。