Merge Intervals
開始から終了までの整数の範囲である区間の集合が与えられます。重なり合う区間の各グループを、グループ全体を含む1つの区間に統合し、開始位置の昇順に並べた統合後の区間を返してください。[1, 4]と[4, 5]のように端点だけが接している区間も、重なり合っているものとして扱います。
区間は同じ長さの2つの配列として与えられます。区間iは[starts[i], ends[i]]です。[start, end]のペアを並べたリストである2次元配列を返してください。
関数
- startsinteger-array
- 各区間の開始
- endsinteger-array
- 各区間の終わりで、その始まりと同じインデックスにある
- 戻り値integer-2d-array
- マージされた区間を [start, end] のペアとして、開始位置順に並べたもの
制約
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- 区間は任意の順序で到着します。
- 端点で接するだけの区間も、重なっているものとして扱います。
例
- 入力
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- 出力
- [[1, 7], [12, 14]]
- 説明
- 開始順に見ると、[1, 4] は [3, 6] と重なり、さらに [5, 7] と重なるため、3つは [1, 7] になります。[12, 14] は 7 より後に始まるため、単独のままです。
- 入力
- starts = [6, 1]ends = [9, 6]
- 出力
- [[1, 9]]
- 説明
- 区間は [6, 9] と [1, 6] です。これらは点 6 を共有しており、接している場合も重なりとして数えるため、[1, 9] に統合されます。
発展問題
区間は開始位置順に並べられ、すでに統合された状態で与えられます。新しい区間を1つ追加してください。再度ソートせずに、O(n) 時間で統合済みのリストを返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
まず、すべての開始位置と終了位置をペアにして、2つの別々の配列ではなく、区間全体を扱えるようにしましょう。
区間を開始位置でソートします。その後、ある区間が重なる可能性があるのは直前のグループだけで、それより前のグループと重なることはありません。
最後に統合した区間を保持しながら、ソート済みの区間を順に処理します。次の区間の開始位置がその区間の終了位置以下なら、終了位置を2つの終了位置の大きい方に設定します。そうでなければ、そのグループは終了し、次の区間で新しいグループを開始します。
解説
任意の順序でペアをマージするには、繰り返し処理が必要です。マージするたびに区間が広がり、すでに確認した区間に届くことがあるためです。代わりに開始位置でソートしましょう。そうすれば、各区間が重なるのは構築中のグループだけになり、1回の処理で完了します。
変化がなくなるまで、重複するペアをマージする
正しいが、最大のテストでは終わらない
考え方
区間 [a, b] と [c, d] は、c ≤ b かつ a ≤ d のとき重なり、[min(a, c), max(b, d)] は両方を包含します。マージするたびに区間が1つ減るため、処理は停止します。また、1回の走査で重なりが見つからなくなれば、残った区間同士に共通点はありません。1回の走査だけでは不十分です。マージ後の区間は幅が広がり、走査中に先ほど比較した小さいほうの区間では届かなかった区間に、届くようになる可能性があります。
1回の走査では約 n²/2 組を比較し、最大で n 回の走査が必要になることがあります。つまり、計算量は O(n³) です。10^4 個の区間を1回走査するだけでも、比較回数はすでに 5 × 10^7 回になります。
アルゴリズム
startsとendsをコピーし、生きている区間の数nを数えます。- 各区間
iを、それより後にあるすべての区間jと比較します。重なっている場合は、iをjを含むように広げ、最後の生きている区間をスロットjに移し、nを1減らします。 - マージした後、スロット
jをもう一度確認します。そこには別の区間が入っているためです。 - マージが発生しないパスが1回できるまで、パスを繰り返します。
- 生きている各開始位置と終了位置を組にし、開始位置で組を並べ替えて返します。
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))開始位置でソートして一度だけ走査する
考え方
開始位置でソートすると、次の区間の開始位置は、末尾が e である最後のグループ内のどの区間よりも早くなることはありません。その開始位置が e 以下なら、グループと重なるか接しているため、そのグループに加わり、e は2つの末尾のうち大きい方になります。開始位置が e より後なら、後続の区間はさらに右から始まるため、どの区間もグループに戻ってくることはありません。グループは完了し、その区間が新しいグループを開始します。
ソートには O(n log n) かかり、走査では各区間を1回ずつ調べます。グループは左から右へ確定するため、結果は開始位置順になります。
アルゴリズム
- 各開始時刻を対応する終了時刻と組み合わせます。区間
iは[starts[i], ends[i]]です。 - 開始時刻でペアをソートします。
- ソートしたペアを順に確認します。結果が空の場合、またはペアの開始時刻が最後にマージした区間の終了時刻より後の場合は、そのペアを新しい区間として追加します。
- それ以外の場合は、最後にマージした区間の終了時刻を、その終了時刻とペアの終了時刻の大きい方に設定します。
- マージしたリストを返します。
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
落とし穴と境界ケース
≤ではなく<で比較する。[1, 4]と[4, 5]のように接する区間は結合しなければならない。- 終了位置を、2つのうち大きい方ではなく、新しい区間の終了位置に設定する。
[1, 10]の後に[2, 3]が続く場合、[1, 10]のままでなければならない。 startsだけをソートしてから、新しい位置のendsを読み取ると、ある開始位置に別の区間の終了位置が対応してしまう。先にペアにするか、インデックスをソートする。- 最後に結合した区間ではなく、直前の入力区間と比較する。
[1, 10]、[2, 3]、[4, 5]の場合、3つ目の区間は[2, 3]とは接しないが、[1, 10]の内側にある。 - Cでは、
*returnSizeに結合後の区間数を設定し、各列のサイズを2に設定するのを忘れない。
よくある質問3
Merge Intervals の時間計算量はどれくらいですか？
ソートとスイープによる解法は、n 個の区間に対して O(n log n) 時間で実行されます。ソートに O(n log n)、スイープに O(n) かかります。ソート済みのペアと結果のために、追加で O(n) の空間を使用します。
なぜ区間を終点ではなく始点でソートするのですか？
[5, 6] は [1, 10] より前に来るため、前方向に走査すると開始時刻を誤って 5 のままにしてしまいます。追加の領域を使わずに区間をマージできますか？
はい、入力を変更してよい場合です。区間をその場でソートし、結合した各区間を同じ配列の先頭から上書きして、最後に書き込んだ区間のインデックスを保持します。時間計算量は O(n log n) のままで、追加で必要な領域は使用する言語のソート処理が使う分だけです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def mergeIntervals(starts, ends):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
期待される出力
[[1, 7], [12, 14]]