Official

F - ダブルブッキング / Double Booking Editorial by leaf1415


【解法1】 ミーティングの予定を開始時刻でソートして判定する方法

入力で与えられるミーティングの予定は、日をまたぐことはありません。よって、それらを開催される日ごとに分類し、 \(i = 1, 2, \ldots, 10^5\) のそれぞれについて、「 \(i\) 日目のミーティングの予定に重複がないか」を判定します。(問題を日ごとに分割することは必須ではありませんが、わかりやすさのためにこのようにします。)

\(i\) 日目のミーティングの予定に重複がないか」は以下の方法で判定できます:
「ミーティングの予定に重複がない」ということは、「新たなミーティングが始まる時刻は必ず直前のミーティングが終了する時刻以降」いうことですから、これが成立しているかを判定します。
\(i\) 日目の予定を、ミーティングの開始時刻 \(S\) でソートしたものを \((S_{p_1}, T_{p_1}), (S_{p_2}, T_{p_2}), \ldots, (S_{p_k}, T_{p_k})\) とします。 このとき、\(i\) 日目の予定に重複がないことは、 すべての \(j = 1, 2, \ldots, k-1\)\(T_{p_j} \leq S_{p_{j+1}}\) が成り立つことと同値ですから、これが成り立つかどうかを確かめれば良いです。


【解法2】 ブール型配列などを用いて予定が入っている時間帯を記録する方法

\(0:00\) 以降かつ \(1:00\) より前の時間帯を「 \(0\) 時台」、 \(1:00\) 以降かつ \(2:00\) より前の時間帯を「 \(1\) 時台」と呼び、 以下同様に、「 \(2\) 時台」 \(\cdots\)\(23\) 時台」と呼びます。
\(1\)日は \(0\) 時台から \(23\) 時台の \(24\) 個の時間帯に分割されます。また、\(S\) 時に開始し \(T\) 時に終了するミーティングの予定は、\(S\) 時台から \(T-1\) 時台を占有します。

以下の方法でこの問題を解きます:
与えられたミーティングの予定を順番に確認していきます。
その過程で、\(i = 1, 2, \ldots, 10^5\) および \(j = 0, 1, \ldots, 23\) について、 「 \(i\) 日目の \(j\) 時台にはすでに予定が入っているか」を大きさ \(10^5 \times 24\) のブール型配列などを用いて記録していきます。 すでに予定が入っている時間帯に、さらにミーティングの予定が入っていることが判明した場合、答えは No と判定します。 一方で、そのようなことがなくミーティングの予定をすべて確認し終えた場合、答えは Yes と判定します。

posted:
last update: