AOJ : 1006 - Boring Commercial

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1006

テレビCMについての問題。
この問題では、途中でCMを見ることなく、連続でどれだけの時間、通常番組を見続けることができるかを答える問題。
開始時間 p から終了時間 q の間で答える。
テレビ局は n 局あり、入力ではそれぞれの局のCMの時間が与えられる。(番組の時間ではないから注意)
この問題の入力の時間は、上位2ケタが hour、下位2ケタが minute で表されているため、時間の計算には注意。

アルゴリズム

コマーシャルであるかないかを示す配列 t を作成。
t[i]が１の場合、i分の時点で、コマーシャルでないことを表す。
t[i]が０の場合、i分の時点で、コマーシャルであることを表す。

配列 t を０で初期化。
テレビ局に関係なく、コマーシャルでない時間１を配列 t に埋める。
配列 t を先頭から見て行って、一番長く１が続く時間を出力する。

プログラム

#include <iostream>
#include <cstring>
using namespace std;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int t[2400];

int toMin(int time){
  return time / 100 * 60 + time % 100;
}

int main(void){
  int n,p,q;

  while(cin>>n>>p>>q && (n||p||q)){
    p = toMin(p);
    q = toMin(q);
    memset(t,0,sizeof(t));

    rep(i,n){
      int m; cin>>m;
      int before = p;

      rep(j,m){
        int ts,te; cin>>ts>>te;
        ts = toMin(ts);
        te = toMin(te);
        if(before <= ts){
          REP(k,before,ts) t[k] = 1;
          before = te;
        }
      }
      if(before <= q){
        REP(j,before,q) t[j] = 1;
      }
    }

    int ans = 0;
    int count = 0;
    REP(i,p,q+1){
      if(t[i]){
        count++;
      }
      else{
        ans = max(ans,count);
        count = 0;
      }
    }
    ans = max(ans,count);
    cout<<ans<<endl;
  }

  return 0;
}