解説動画: youtu.be
テレビ番組を録画したい
- N個のテレビ番組を録画したい
- チャンネルはC個
- i個のテレビ番組は、時刻s~時刻tまで、チャンネルCiで放送される
- 録画機は、時刻S~時刻Tまで録画したいとすると、S-0.5~Tまでの時間、他のチャンネルの録画をすることができない(同じチャンネルならできる)
- N個すべてを録画するとき、必要な録画機の最小数は?
解き方
累積和を使う
- 配列aを用意する
- 変数bを一つ用意する
- すべての番組の最を1とする
- その番組の終わりに-1とする
- a配列を順に追う 1があったらbに+1,-1なら-1を足していく
- bの最大値を求める
ほへーって感じです。ほへー。
累積和はアルゴリズムの一つのようです。