atcoder.jp
最終的に選んだものは、小さい方から取っていくのが最適だと証明可能.
ということで、最小の値 X を固定したらそこから貪欲に取れば良い.
「X 未満の値は取れない ⇔ X未満の値を跨ぐような区間を選べない」
ゆえに X 未満の値がある場所で分割してしまえば、より小さなサイズの問題になる.
しかも小さなサイズの問題の中では、この分割された区間内の最小値がこの区間から選ばれる最小値と考えて良く、貪欲に取ればいいのでソートするだけで十分である.
区間を分割するアイデアが思い浮かばなかったとです...
