Meeting Rooms
会議のリストが2つの配列として与えられます。会議 i は starts[i] から ends[i] まで行われます。ある人がすべての会議に出席したいと考えています。そのため、会議が重なってはいけません。ある会議の終了と同じ時刻に、別の会議を開始することはできます。その人がすべての会議に出席できる場合は true を、そうでない場合は false を返してください。
関数
- startsinteger-array
- 各会議の開始時刻
- endsinteger-array
- 各会議の終了時刻（開始時刻と同じインデックスにあります）
- 戻り値boolean
- 会議が重複していなければ true、そうでなければ false
制約
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- 会議は並べ替えられていません。2つの会議が同一である場合があります。
例
- 入力
- starts = [9, 13, 10]ends = [10, 15, 12]
- 出力
- true
- 説明
- 時間順では、会議は9時から10時、10時から12時、13時から15時まで行われます。2つ目の会議は1つ目の会議が終わると同時に始まりますが、これは許可されているため、答えは
trueです。
- 入力
- starts = [1, 4, 7]ends = [5, 6, 8]
- 出力
- false
- 説明
- 1時から5時までの会議は4時の時点でもまだ続いており、4時から6時までの会議が始まるため、答えは
falseです。
提出時に隠しテスト+15件
発展問題
会議が1件ずつ予約される場合、すべてを再び並べ替えることなく、新しい予約をそれぞれスケジュールと照合して O(log n) で確認するにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
時間が重なる2つの会議には、共通する時間帯があります。隣り合う会議の間に重なりが生じるように、会議をどのような順序で並べられますか？
会議を開始時刻順に並べます。すると、会議が重なる可能性があるのは直前の会議だけです。直前の会議が終わった後に始まるなら、それより前のすべての会議が終わった後にも始まります。
各会議の開始時刻と終了時刻の組み合わせを保ったまま、開始時刻で並べ替えます。並べ替えたリストを順に確認し、各開始時刻をその直前の会議の終了時刻と比較します。開始時刻が終了時刻より小さい場合は重複していますが、終了時刻と等しい場合は問題ありません。
解説
すべての会議のペアを確認すれば、衝突があるかどうかを見つけられますが、O(n²) のコストがかかります。開始時刻で並べ替えると、確認すべき内容が変わります。会議が衝突するのは、並べ替えた順序で隣り合う会議同士だけなので、各会議につき1回比較すれば十分です。
すべてのペアを比較する
正しいが、最大のテストでは終わらない
考え方
一方の会議がもう一方の終了時刻より前に始まる場合、2つの会議は重なります。1時から5時までの会議と4時から6時までの会議では、1は6より前で、4は5より前なので、重なります。9時から10時までの会議と10時から12時までの会議では、10は10より前ではないため、重なるのではなく、ちょうど接するだけです。
両側で厳密な < を使うことで、ある会議が別の会議の終了と同時に始まることができます。すべてのペアをテストし、最初に重なりが見つかった時点で false を返します。
問題はペアの数です。会議が n = 5000 件あると、ペアは約1,250万組あります。重なりのないスケジュールでは、そのすべてを確認する必要があり、最大規模のテストでは遅すぎます。
アルゴリズム
- 各インデックス
iと、それより後のすべてのインデックスjについて: starts[i] < ends[j]かつstarts[j] < ends[i]の場合、2つの会議は重なっています:falseを返します。- 重なるペアがなければ、
trueを返します。
def canAttendMeetings(starts, ends):
n = len(starts)
for i in range(n):
for j in range(i + 1, n):
# two meetings clash when each one starts before the other ends
if starts[i] < ends[j] and starts[j] < ends[i]:
return False
return True開始位置で並べ替えて隣接する要素を確認する
考え方
各会議の開始時刻と終了時刻の対応を保ったまま、開始時刻順に並べ替えます。次に、任意の会議とその直前の会議を見ます。前の会議が後の会議の開始時刻より後に終わるなら、重なっています。そうでなければ、後の会議は前の会議が終わる時刻以降に始まります。
なぜ確認が必要なのは隣り合う会議だけなのでしょうか？ それまでのすべての会議が、そのひとつ前の会議の終了時刻以降に始まっているなら、それまでの会議は重なっておらず、直前の会議が最も遅く終わります。その終了時刻以降に始まる新しい会議は、それらすべての会議の終了時刻以降に始まります。
最初の例では、並べ替えた会議は 9 から 10、10 から 12、13 から 15 です。開始時刻 10 は終了時刻 10 より前ではなく、開始時刻 13 は終了時刻 12 より前ではないため、重なりはありません。同じ開始時刻の会議は必ず重なります。すべての会議は少なくとも 1 単位の長さがあり、この確認でも検出できます。
並べ替えの計算量は O(n log n) で、走査の計算量は O(n) です。会議の対応関係を保ったコピーに必要な空間は O(n) です。
アルゴリズム
- 各開始時刻を対応する終了時刻と組み合わせます。
- 開始時刻順にペアを並べ替えます。
- 最初の会議以降について、それぞれの開始時刻を直前の会議の終了時刻と比較します。
- 開始時刻のほうが小さい場合は、
falseを返します。 - ループの後、
trueを返します。
def canAttendMeetings(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
for i in range(1, len(meetings)):
# a meeting must not start before the one right before it ends
if meetings[i][0] < meetings[i - 1][1]:
return False
return True
落とし穴と境界ケース
よくあるバグは、どの開始時刻と終了時刻を比較するか、また、会議が接する場合をどう扱うかに関するものです。
startsを並べ替えて、endsを入力順のままにする。各終了時刻は対応する開始時刻と一緒に移動させる必要があります。そうしないと、ある開始時刻と別の会議の終了時刻を比較してしまいます。<ではなく≤を使う。9時から10時までの会議と10時から12時までの会議は接していますが、重なってはいません。その場合の答えはtrueです。- 入力順のまま、各会議が次の会議の開始前に終了することだけを確認する。入力は並べ替えられていないので、入力で隣り合う会議からは何もわかりません。
starts[j] < ends[i]のように、1つの条件だけで組み合わせを判定する。これは会議jの開始が後の場合にしか成り立ちません。たとえば、5時から6時までの会議と0時から1時までの会議がこの順に並んでいる場合、0 < 6によって、実際にはない重なりが報告されます。
よくある質問4
Meeting Rooms の時間計算量はどれくらいですか？
会議を開始時刻でソートするには O(n log n) かかり、隣り合う会議を比較しながら進む処理は O(n) かかるため、合計は O(n log n) です。すべてのペアを比較すると、代わりに O(n²) かかります。
なぜ各会議をその直前の会議と比較するだけで十分なのでしょうか？
開始時刻でソートした後、これまでに重複が見つかっていなければ、これまでの会議は、それぞれが前の会議の終了時刻以降に始まる連鎖を形成します。連鎖の最後の会議が最も遅く終了します。その終了時刻以降に始まる新しい会議は、それ以前のどの会議とも重複しません。
端が接する会議は重なっていると見なされますか？
この問題では該当しません。ある会議が別の会議の終了とまったく同じ時刻に開始してもかまいません。そのため、判定には厳密な start < previous end を使います。会議が重なることを禁止する場合は、判定は start ≤ previous end になります。
会議室の最小数はどのように求めますか？
開始時刻と終了時刻を別々のリストとして並べ替え、両方を順に見ていきます。開始時刻ごとに部屋を1つ使い、次の開始時刻までに来る終了時刻ごとに部屋を1つ空けます。同時に使用中となる部屋の最大数が答えです。ここで「はい」か「いいえ」で答える質問は、部屋が1つで足りるかどうかを尋ねるのと同じです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def canAttendMeetings(starts, ends):
# ここにコードを書いてくださいケース1
ケース2
入力
starts = [9, 13, 10] ends = [10, 15, 12]
期待値
true