AT_tenka1_2012_7 席が足りない

[problemUrl]: https://atcoder.jp/contests/tenka1-2012-qualB/tasks/tenka1_2012_7 急成長中の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 $ 行で出力せよ。 なお、行の終端には改行が必要である。 ``` 3 10:00 12:00 12:00 14:00 14:00 18:00 ``` ``` 1 ``` - 出社時刻・退社時刻が同じ場合は席をシェアすることができる。 ``` 3 00:00 09:00 08:00 17:00 16:00 25:00 ``` - $ 25:00 $ は翌日 $ 01:00 $ を意味する。 - この場合、この $ 3 $ 人は席をシェアすることができない。 ``` 3 ``` ``` 4 00:00 07:00 06:00 13:00 12:00 19:00 18:00 25:00 ``` ``` 2 ```

N/A

N/A