AOJ 1006 Boring Commercial
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1006
n個のテレビ局がCMを流す時間を与えられる。この時、与えられる時間範囲の中で、チャンネルを操作すればCMを見ずにすむ最長連続時間はいくらかを求める問題。
与えられる時間がデジタル時計形式なので、そこは0時00分から何分かに直して処理した。また、ある時間にCMを流していないテレビ局があるかはCMを流しているテレビ局がnより少ないかどうかで判定できる。
typedef pair<int,int> PI; main(){ int n,s,g; while(cin>>n>>s>>g,n|s|g){ s=s/100*60+s%100; g=g/100*60+g%100; vector<PI> cha; rep(i,n){ int t; cin>>t; while(t--){ int ts,tg; cin>>ts>>tg; ts=ts/100*60+ts%100; tg=tg/100*60+tg%100; cha.pb(mp(ts,tg)); } } int ans=0; int tlen=0; for(int i=s;i<g;i++){ int cm=0; rep(j,cha.size())if(cha[j].F<=i && i<cha[j].S)cm++; if(cm<n)++tlen; else tlen=0; ans=max(ans,tlen); } cout<<ans<<endl; } }