きろく

特筆すべき記録のまとめ

AtCoder Regular Contest 032:C - 仕事計画

問題

C - 仕事計画

a_i と b_i を始点・終点とする区間が N 個あり,それらからいくつか両端以外で重ならないように選ぶとき,最大でいくつ選べるかを求め,辞書順最小の組み合わせを求める問題.

解法

区間をソートし,時間を後ろから見ていく.今見ている時間から始まる区間は std::lower_bound, std::upper_bound() で求まるので,それらの終点から選べる区間の数の max を取る.このとき,区間の index が出来るだけ小さくなるように max を取る.あとは,今見ている時間から始まる区間を取らない場合は,今見ている時間 + 1 の結果を用いればよい.この2つで最適な方を今見ている時間の結果にすればよい.最後に,これらの結果を用いて,最初から区間を選ぶ経路を復元すればよい.O(MlogN + N).

解答

Submission #3167751 - AtCoder Regular Contest 032

f:id:babcs2035:20180909155445p:plain

gist.github.com