ABC080 D Recording
問題概要
個のテレビ番組を録画したい。
テレビが受信できるチャンネルが 個あり、1から
までの番号がついている。
録画したいテレビ番組のうち、 個目のテレビ番組は、時刻
から時刻
までチャンネル
で放送される（時刻
を含み時刻
を含まない）。同じチャンネルで複数のテレビ番組が同時に放送されることはない。
また、録画機は、あるチャンネルの時刻 から時刻
までを録画するとき、時刻
から時刻
までの間、他のチャンネルの録画に使うことができない(ただし時刻
を含み時刻
を含まない）。
必要な録画機の最小個数を求めよ。
制約
解法
はじめは と
を無視してimos法したら解けるんじゃないかと思ったけど、2ケースWA。
いろいろ考えてるうちに、
2 1
1 2 1
2 3 1
のケースでダメなことがわかる。
この例でいくと、時刻1から時刻3までを録画したいから、時刻0.5から時刻3までを1つの録画機で録画したいけど、「時刻0.5から時刻2」「時刻1.5から時刻3」の2つを録画することになって、2個の録画機が必要という答えが出てしまう。
つまりチャンネルの情報は不要じゃなかった。
ということで、
v[ ][
] := チャンネル
で時刻
に録画機を使う
という配列を作って、各チャンネルでimos法をする。
このときは、開始時刻を ではなく
と考えてimos法をして、あとから録画開始時刻を1だけ早める（これで、同じチャンネルで連続して録画するときに重複をなくせる）。
あとは各時刻について、いくつのチャンネルで録画機が必要かを計算する。
計算量は 。
