ABC080 D - Recording
解法
まずは、同一チャンネル内で区間が連続するもの、つまりとをまとめてのようにしてしまいます。これは、それぞれのチャンネルについて区間をわけ、そして開始時間の昇順でソートをして前から見ていき、今見ている区間の終わりの時間と次の区間の始まりの時間が同時刻であれば合体、というようにしていけばよいです。
あとは、いもす法を用いて、時刻で必要な録画機の個数を調べていき、その最大値をとれば完成です。
今回、0.5という数字がでてきているので、すべての時刻を2倍してあげます。すると、という区間の録画には、
から、という閉区間で録画機が必要になります。
なので、時刻で必要な録画機の個数、とすると、に1追加し、から1減算をすることで、あとはについて、はじめから累積和をとっていけば、を完成させることができます。
あとは、全てののうち最大値をとることで、答えとなります。の配列は、時刻を2倍していることから、とりうる時刻の最大値の2倍だけ要素数が必要なことに注意してください。