AOJ_2013

最初、一日はたかだか864000秒しかないことを利用して解こうとしたが
なぜかWrongAnswerだらけになるので、あきらめた。
結局、自力では解けなかった。
列車が行くとインクリメント、着くとデクリメントというやりかたでいけるらしいので
やってみたらAC。
思いつけない…orz

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int N;
typedef pair<int ,int> P; //.second==1着時刻  .second==2発時刻
priority_queue<P, vector<P>, greater<P> > train; // 時刻を小さい順に取り出す

int hms2s(int h, int m, int s){
	return h * 3600 + m * 60 + s;
}
int main(){
	while(scanf("%d", &N)){
		if(N == 0) return 0;
		for(int i = 0; i < N; i++){
			int h, m, sec;
			scanf("%d:%d:%d", &h, &m, &sec); //発時刻
			int s = hms2s(h, m, sec);
			scanf("%d:%d:%d", &h, &m, &sec); //着時刻
			int t = hms2s(h, m, sec);
			train.push(P(t, 1));
			train.push(P(s, 2));
		}
		int ans = 0, res = 0;
		for(int i = 0; i < N * 2; i++){
			P p = train.top(); train.pop();
			if(p.second == 1){
				res--; //到着なら減らす
			}else{
				res++; //発なら増やす
			}
			ans = max(ans, res);
		}
		printf("%d\n", ans);
	}
	return 0;
}