AOJ 2013 - Osaki

Osaki
提出コード
発車時刻と到着時刻のペアを入力しているわけではない上、入力時点ではソートされているわけではないことに注意します。
というわけで、入力を受け取るときは、発車時刻、到着時刻それぞれ別でまとめておき、入力後にそれぞれソートします。それぞれ、00:00:00から何秒後か、というようになおしておくとソートしやすく、その後でも使いやすいと思います。
ソートを終えたら、最悪のパターン、つまり同時に電車が動いている時間が一番多いパターンを調べます。
最初からi番目に発車した電車は、最初からi番目に到着する、という条件を加えるとき、同時に動いている電車の数を最も少なくできるので、i番目の電車が到着する予定の時刻までに、同時に動かしていないといけない電車の最悪の台数をdp[i]とすると、
dp[i] = max(dp[i-1],(i番目以降に出発する電車の中で、i番目の電車が到着する時刻より前に発車するものの個数))
となります。
あとはiを動かして全探索すれば終わりです。