No.580 旅館の予約計画

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 36
作問者 : horiesinitihoriesiniti / テスター : ukuku09ukuku09
2 ProblemId : 1938

問題文

ある旅館では月初めと9日目を休みとし、2日から8日までの客の予約をとる。

客は2日目の00時00分から8日目の23時59分までのいずれかの範囲内で予約をとる。

旅館の1人用個室数$n$、$m$人の客のチェックインとチェックアウトの予約日時が分単位までで与えられる.

泊まる客の人数を最大化することを目指した時何人泊まれるか算出してほしい。

チェックアウト後、部屋の清掃があるため次の客が入れるのはチェックアウト時刻から1分の間隔は空ける必要があるとする。

例えば客が12時にチェックアウトした部屋は12時に予約した客はその部屋に入れない。 12時1分から予約が有効であるとする。


この問題はHackerRankで公開した自作問題をHackerRank公式,yukicoder公式両方の許可を得て転載し一般問題とし公開となっています。

入力

$n$ $m$
$d_1$ $hh_1$:$mm_1$ $o_1$ $hho_1$:$mmo_1$
$\dots$
$d_i$ $hh_i$:$mm_i$ $o_i$ $hho_i$:$mmo_i$
$\dots$
$d_m$ $hh_m$:$mm_m$ $o_m$ $hho_m$:$mmo_m$

$n$は一人用部屋の個数、$m$は予約の人数。
$0 < n < 101$
$0 < m < 1001$
続く$m$行は顧客のチェックインとチェックアウトの日時である。
$d_i$ $hh_i$ $mm_i$はチェックインの日時分である。
$d_i$は日付 $1 < d_i < 9$
$hh_i$は時間 $00 \leq hh_i < 24$
$mm_i$は分 $00 \leq mmi < 60$
$o_i$ $hho_i$ $mmo_i$はチェックアウトの日時分である。
$o_i$は日付 $1 < oi < 9$
$hho_i$は時間 $00 \leq hhoi < 24$
$mmo_i$は分 $00 \leq mmoi < 60$
チェックアウトはチェックインより後か同じ時刻と仮定してよい。
チェックインと同じ時刻にチェックアウトする場合も、チェックアウトした一分後からその部屋の予約が可能であるとする。
この場合客は1分以下だけ部屋を使い、1分の残り時間で神業で部屋の清掃が行われたと仮定してよい。
出力$U$は泊まる人数を最大化するよう予約をやりくりした時の宿泊人数を一行に答えよ。

出力

$U$ 最後に改行してください。

サンプル

サンプル1
入力
1 3
3 10:00 3 10:00
3 10:00 3 10:00
3 10:01 3 10:02
出力
2

部屋は一部屋しかない。 10時に泊まる客が使用し、10時1分からの客が泊まって二人である。

サンプル2
入力
2 7
3 12:30 4 15:30
3 16:30 3 16:30
3 16:31 4 15:29
4 15:30 7 15:30
2 02:00 3 15:29
3 15:10 4 15:29
3 12:47 4 14:27
出力
5

2部屋をやりくりすると5人が泊まれる。

サンプル3
入力
3 11
3 12:30 4 15:30
4 15:31 5 16:20
5 16:21 6 17:30
3 12:30 4 15:30
4 17:30 6 03:30
7 12:10 8 23:59
2 14:40 4 15:30
5 16:40 7 12:20
8 00:00 8 17:54
8 17:54 8 17:55
2 12:00 7 03:30
出力
10

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。