C - 席が足りない 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

急成長中のK社は、ハイペースで採用しすぎて席が足りなくなってしまいました。
次のオフィスの移転先は決まっているのですが、それまでは少ない席をやりくりしないといけません。

幸い、社員の生活リズムがバラバラなので、ある人が退社したあとに別の人が出社するなら席をシェアすることにしました。
しかし、出社から退社まで席を移動しないようにしたいです。

また、プロジェクトごとにまとまって座りたいと考えています。
プロジェクトの社員全員がそのプロジェクトに割り当てられた席に座り、
それ以外の社員がそのプロジェクトに割り当てられた席に座ることがないようにしたいです。

あるプロジェクトの社員それぞれの出社時間と退社時間が与えられるので、
そのプロジェクトには最低何席割り当てる必要があるかを求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
N
Ts_1 Te_1
Ts_2 Te_2
:
:
Ts_N Te_N
  • 入力は N+1 行ある。
  • 1 行目には、社員数を表す N ( 1 \leq N \leq 15 ) が与えられる。
  • 2 行目からの N 行には i ( 1 \leq i \leq N ) 番目の社員の出社時間 Ts_i ( 00:00 \leq Ts_i \leq 23:59 ) と退社時間 Te_i ( Ts_i \lt Te_i \leq 35:59 ) が空白区切りとして与えられる。
  • Te_i \geq 24:00 は翌日を意味する。
  • 出社から退社までの時間が 24 時間以上になることはない。

部分点

プロジェクトの社員が少ない入力 ( 1 \leq N \leq 8 ) のみ正解すると、100 点満点に対して部分点として 20 点が与えられる。
また、すべての社員が 23:59 までに退社する入力 ( 1 \leq i \leq N に対し Te_i \leq 23:59 ) のみ正解すると、100 点満点に対して部分点として 30 点が与えられる。
上記 2 条件のいずれかを満たす入力すべてに正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

最低限プロジェクトに割り当てる必要のある座席の数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

3
10:00 12:00
12:00 14:00
14:00 18:00

出力例 1

1
  • 出社時刻・退社時刻が同じ場合は席をシェアすることができる。

入力例 2

3
00:00 09:00
08:00 17:00
16:00 25:00
  • 25:00 は翌日 01:00 を意味する。
  • この場合、この 3 人は席をシェアすることができない。

出力例 2

3

入力例 3

4
00:00 07:00
06:00 13:00
12:00 19:00
18:00 25:00

出力例 3

2

出典

天下一プログラマーコンテスト2012 予選B