Problem 2013 : Osaki

問題概要

日本語なので本文参照。（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2013&lang=jp）

電車の発車時刻と到着時刻の表が与えられたとき、必要な電車の数を求める。

解法

区間スケジューリングの典型問。
すなわち、終了時間の早い順にタスクをソートし、重なりが最も大きくなる部分の重なりを答えればよい。

ソースコード

char in[20];
int n;
pi t[20000];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)rep(j,2)
		{
			int h,m,s; scanf("%d:%d:%d",&h,&m,&s);
			t[i*2+j]=mp(h*3600+m*60+s,1-j);
		}
		sort(t,t+2*n);
		
		int ans=0,c=0;
		rep(i,2*n)
		{
			if(t[i].second)c++; else c--;
			ans=max(ans,c);
		}
		printf("%d\n",ans);
	}
	return 0;
}