SRM 645 Div1 Easy JanuszTheBusinessman - yoshiokatsuneoのブログ

[問題]

365日の中に、重なるかもしれないN個の区間がある。いくつかの区間を選び、すべての区間が選択した区間と重なるようにしたい。最小でいくつの区間を選べばよいか？

2≤N≤50

[解答](後で)

区間を終了日順でソートして未決定区間とする。

未決定区間の中の最初の区間と交わる区間の中で、(未決定区間以外を含む全ての区間から)終了日が一番遅いものを選択する。選択した区間と交わるものを未決定区間から省く。

これを未決定区間がなくなるまで繰り返す。

[コード](C++)

[感想]

本番は「(未決定区間以外を含む全ての区間から)終了日が一番遅いもの」の所を「(未決定区間の中での)終了日の一番遅いもの」としてしまい失敗。注意不足。。。

けど、失敗した人が多かったようで、レーティングはあまり下がらず。