Meeting Rooms II
会議のリストが2つの配列として与えられます。会議 i は starts[i] から ends[i] まで行われます。1つの部屋で同時に行える会議は1つだけですが、別の会議がその部屋で終了するちょうどその時点から、会議を開始できます。
すべての会議を収容できる最小の部屋数を返す、minMeetingRooms という名前の関数を書いてください。
関数
- startsinteger-array
- 各会議の開始時刻
- endsinteger-array
- 各会議の終了時刻（開始時刻と同じインデックスにある）
- 戻り値integer
- すべての会議を収容できる最少の部屋数
制約
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- 会議はソートされていません。2つの会議が同一の場合もあります。
例
- 入力
- starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
- 出力
- 3
- 説明
- 時刻 4 には、1 から 5、2 から 6、4 から 8 までの会議がすべて実施中なので、少なくとも
3室必要です。3 室あれば十分です。7 から 9 までの会議は、5 時に空く部屋を使います。
- 入力
- starts = [12, 10, 14]ends = [14, 12, 16]
- 出力
- 1
- 説明
- 会議は10時から12時、12時から14時、14時から16時まで行われます。それぞれの会議は直前の会議が終わった瞬間に始まるため、1つの部屋ですべての会議を行えます。
- 入力
- starts = [0, 2, 3]ends = [10, 3, 5]
- 出力
- 2
- 説明
- 0から10までの会議は、その間ずっと1つの部屋を使用します。2から3までの会議には2つ目の部屋が必要で、3から5までの会議は、その部屋が空くと同じ部屋を使うため、
2部屋で十分です。
提出時に隠しテスト+17件
発展問題
答えの部屋数を超えずに、各会議がどの部屋に割り当てられるかも示せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの時点でも、進行中の会議にはそれぞれ専用の部屋が必要です。その日の最も忙しい時間帯から、答えについて何が分かりますか？
開始時刻順に会議を確認します。会議が始まるとき、確認する価値があるのは、最初に空く部屋だけです。
- 各部屋の終了時刻を最小ヒープに保持します。最小の終了時刻が次の開始時刻以前であれば、その部屋は空いています。その終了時刻を新しい会議の終了時刻に置き換えます。そうでなければ、新しい終了時刻を追加します。ヒープのサイズが答えです。
解説
必要な部屋数は、同時に行われている会議の最大数です。すべての開始時刻について、その時点で行われている会議を数えると、O(n²)かかります。ソートすれば、1日の予定を一度たどるだけで済みます。部屋が空く時刻を格納した最小ヒープ、または開始時刻と終了時刻をそれぞれソートした2つのリストを使えば、O(n log n)で答えが求まります。
各開始時刻に実行中の会議数を数える
正しいが、最大のテストでは終わらない
考え方
どの時点でも、開催中の各会議にはそれぞれ部屋が必要です。そのため、同時に開催されている会議の最大数と同じ数以上の部屋が必要です。また、その数があれば十分です。開始時刻順に部屋を割り当て、すべての部屋が使用中になったときだけ新しい部屋を用意すれば、その時点でちょうどその数の会議が開催されていることになります。
開催中の会議数が増えるのは会議が始まるときだけなので、最も混み合うのは何らかの会議が始まる時点です。各会議 i について、starts[j] ≤ starts[i] < ends[j] を満たす会議 j の数を数えます。つまり、すでに始まっていて、まだ終了していない会議です。starts[i] とちょうど同じ時刻に終わる会議は数えません。その時点で部屋が再び空くからです。
最初の例では、時刻 4 に、1 から 5 までの会議、2 から 6 までの会議、4 から 8 までの会議が開催中です。合計 3 つです。時刻 7 には、4 から 8 までの会議と 7 から 9 までの会議だけが開催中です。合計 2 つです。最大数は 3 です。
n 個の会議それぞれについて、すべての n 個の会議を調べます。n = 5000 の場合、チェック回数は 2,500 万回です。C では 1 秒未満、Python や R では数秒かかり、n が 2 倍になるたびに、その 4 倍の時間がかかります。
アルゴリズム
- 各会議
iについて、runningを0に設定します。 - 各会議
jについて、starts[j] ≤ starts[i] < ends[j]の場合、runningに 1 を加えます。 - これまでに確認した
runningの最大値を保持します。 - その最大値を返します。
def minMeetingRooms(starts, ends):
n = len(starts)
most = 0
for i in range(n):
# how many meetings are running at the moment meeting i starts
running = 0
for j in range(n):
if starts[j] <= starts[i] < ends[j]:
running += 1
most = max(most, running)
return most部屋が空く時刻の最小ヒープ
考え方
フロントデスクの担当者のように部屋を割り当てます。会議を開始時刻順に処理します。それぞれの会議について、最初に空く部屋を確認します。会議の開始時刻までに空いていれば、その部屋を割り当てます。そうでなければ、すべての部屋がまだ使用中なので、新しい部屋を用意します。
その部屋だけを確認すれば十分です。最初に空く部屋がまだ使用中なら、すべての部屋が使用中です。空いているなら、どの空き部屋を使っても同じです。これから始まる会議の開始時刻は今と同じか、それより後なので、今空いている部屋はどれも、その会議まで空いたままです。
必要なのは、各部屋の中で最も早い空き時刻です。その時刻は会議ごとに変わります。最小ヒープは、各部屋の終了時刻を1つずつ保持し、その中で最小の値を取り出せます。部屋を再利用するときは、その終了時刻を新しい会議の終了時刻に置き換え、新しい部屋を用意するときは、新しい終了時刻を追加します。最初の例では、開始時刻順に並べると、1から5では[5]、2から6では[5, 6]、4から8では[5, 6, 8]となり、7から9では5が7以下なのでそれを置き換え、[6, 8, 9]が残ります。部屋は3つです。
ソートにはO(n log n)かかり、各会議ではO(log n)のヒープ操作を1回行います。Pythonのheapq、JavaのPriorityQueue、C++のgreaterを使ったpriority_queue、RustのReverseを使ったBinaryHeap、Goのcontainer/heap、PHPのSplMinHeapを使えば、ヒープを利用できます。ほかの言語では配列で管理します。インデックスiの親は(i-1)/2にあり、値は親より小さい間、上へ移動します。
アルゴリズム
- 各会議の開始時刻と終了時刻を対応させたまま、開始時刻順に会議をソートします。
- 各会議について、ヒープが空でなく、最小の終了時刻が会議の開始時刻以前であれば、その終了時刻を会議の終了時刻に置き換えます。
- そうでなければ、会議の終了時刻をプッシュします。新しい部屋が開きます。
- 部屋ごとに1つの要素があるヒープのサイズを返します。
import heapq
def minMeetingRooms(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
free_at = [] # a min-heap: when each room's last meeting ends
for start, end in meetings:
if free_at and free_at[0] <= start:
heapq.heapreplace(free_at, end) # the earliest free room is free now: reuse it
else:
heapq.heappush(free_at, end) # every room is busy: open a new one
return len(free_at)開始時刻と終了時刻を別々に並べ替える
考え方
ヒープでは、どの終了時刻がどの部屋に対応するかを管理しますが、求める答えは部屋数だけです。会議が始まるときに重要なのは、それまでに終了して部屋を空けた会議があるかどうかだけで、どの会議だったかは関係ありません。そこで、開始時刻と終了時刻を別々のリストとしてソートし、開始時刻のリストをたどりながら、終了時刻のリストを指すポインター ended を使います。
開始時刻を順に見ていきます。それが endTimes[ended] 以上なら、その時点までに会議が終了しています。その部屋を新しい会議に割り当て、ended を次に進めます。そうでなければ、使用中の部屋はすべてまだ埋まっているため、rooms を1増やします。各開始時刻が使う終了時刻は最大1つで、ヒープで部屋を再利用するときに古い終了時刻を新しい終了時刻に置き換えるのと同じです。
最初の例では、開始時刻は1、2、4、7、終了時刻は5、6、8、9です。開始時刻1、2、4はいずれも終了時刻5より前なので、rooms は3まで増えます。開始時刻7は5以上なので、その部屋を再利用し、ended は終了時刻6に進みます。答えは3です。≥ があることで、終了と開始が同時刻の会議は同じ部屋を使えます。2つ目の例では、開始時刻12の会議が終了時刻12の会議と重なり、その部屋を再利用します。
この数が実際の最大値を超えることはありません。rooms が増えるとき、次の終了時刻はまだ先なので、その時点ですべての rooms 個の会議が進行中です。また、実際の最大値にも達します。開始時刻が部屋を新たに使わないのは、それ以前または同時刻に実際の会議が終了し、部屋が空いた場合だけだからです。2回のソートに O(n log n)、走査に O(n)、ソート済みのコピーに O(n) の空間が必要です。
アルゴリズム
- 開始時刻のコピーと終了時刻のコピーをそれぞれソートします。
roomsとendedを0に設定します。- 開始時刻を順に確認し、
endTimes[ended]以降であれば、endedに 1 を加えます。この会議は空いた部屋を使います。 - そうでなければ、
roomsに 1 を加えます。 roomsを返します。
def minMeetingRooms(starts, ends):
start_times = sorted(starts)
end_times = sorted(ends)
rooms = 0
ended = 0 # how many meetings have ended, earliest end first
for start in start_times:
if start >= end_times[ended]:
ended += 1 # a meeting has ended by now: this one takes its room
else:
rooms += 1 # every room is busy: open a new one
return rooms
落とし穴と境界ケース
バグの多くは、会議の終了時刻と開始時刻が一致する場合の比較や、どの部屋を確認するかにあります。
start > endと確認し、start ≥ endとしない。すると、会議は部屋が空いた瞬間にその部屋を使えません。10時から12時、12時から14時、14時から16時の会議には、部屋が1つではなく2つ必要になります。- 最初に空く部屋ではなく、最後に開いた部屋を確認する。1時から3時、2時から10時、4時から6時の会議の場合、最後に開いた部屋は10時まで使用中なので、最初の部屋が3時から空いているにもかかわらず、3つ目の部屋を開くことになります。
- 1つの会議と重なる会議の最大数に1を足す。0時から10時の会議は、2時から3時と3時から5時の会議と重なりますが、この2つの会議同士は重ならないため、必要なのは3部屋ではなく2部屋です。
- 2つのソート方法を混同する。ヒープでは、開始時刻でソートする前に各終了時刻を対応する開始時刻と組にする必要があります。一方、2つのリストを使う方法では、開始時刻と終了時刻を意図的に別々にソートします。
よくある質問4
Meeting Rooms II の時間計算量は何ですか？
どちらの高速な解法も O(n log n) で実行されます。ヒープを使う方法では会議をソートし、会議ごとに O(log n) のヒープ操作を1回行います。2つのリストを使う方法では2回ソートし、O(n) の走査を1回行います。どちらも追加の領域として O(n) を使用します。開始時刻ごとに進行中の会議を数える方法は O(n²) です。
なぜ min-heap で Meeting Rooms II を解決できるのでしょうか？
開始時刻順に会議を処理する場合、確認する価値があるのは最初に空く部屋だけです。終了時刻の最小ヒープを使えば、その部屋を O(1) で取得でき、更新は O(log n) で行えます。ヒープが大きくなるのは、すべての部屋が使用中の場合だけなので、最終的なサイズが必要な部屋数の最小値になります。
Meeting Rooms IIはヒープを使わずに解けますか？
はい。開始時刻と終了時刻を別々のリストとして並べ替え、終了時刻のリストを指すポインターを使って開始時刻を順に確認します。次に使える終了時刻以降に始まる予定は部屋を再利用し、それ以外の予定では部屋を新たに使います。同じ考え方はスイープラインとしても使えます。各予定を開始時刻の +1 イベントと終了時刻の -1 イベントに変換し、時刻が同じ場合は開始イベントより先に終了イベントを処理して、推移する合計の最大値を記録します。
答えは、同時に重なる会議の最大数と同じですか？
はい。同じ時刻に行われる会議には別々の部屋が必要なので、少なくともその数の部屋が必要です。開始時刻順に各会議へ空いている部屋を割り当てれば、それ以上は必要ありません。そのため、重複する会議数の最大値がそのまま答えになります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def minMeetingRooms(starts, ends):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
starts = [4, 1, 7, 2] ends = [8, 5, 9, 6]
期待値
3