ABC214 E Packing Under Range Regulations
まず, 入力の$ L_i, R_iを合わせて座標圧縮しておく. すると, 区間の左端・右端にあたるタイミングは全探索できるようになる. ここで, 与えられた条件を「時刻$ L_iから$ R_iの間に行わなければならない仕事」ととらえると, 締め切りの早い順に貪欲法を適用すればよいことがわかる. 実装の際はpriority_queueを持っておくことで効率的に処理することができる.
よって, この問題をクエリ当たり$ O(N \log N)で解くことができた.