Kodaman コンテスト：J - 異世界転生2

問題

https://www.hackerrank.com/contests/kodamanwithothers/challenges/2-82

解法

まず，仕事を開始時刻が早い順にソートしておく．次に，以下の DP を考える．

dp(i) := 次に i 番目の仕事をすることが可能な時，i 番目以降の仕事で得られる嬉しさの和の最大値

遷移は i 番目の仕事をするかどうかの 2 通り．仕事をする場合，i 番目の仕事の終了時刻以上であって最も早く始まる仕事を二分探索で求め，その仕事へ遷移させる．O(NlogN)．

解答

https://www.hackerrank.com/contests/kodamanwithothers/challenges/2-82/submissions/code/1316479002