Insert Interval
開始位置でソートされた区間が2つの配列として与えられます。区間 i は [starts[i], ends[i]] であり、どの2つの区間も重なったり接したりしていません。新しい区間 [newStart, newEnd] を挿入し、重なるか接するすべての区間と結合して、開始位置でソートされた [start, end] のペアとしてすべての区間を返してください。
一方の区間の終点がもう一方の区間の始点と同じ場合、区間は接します。たとえば [2, 4] と [4, 8] のような場合です。接する区間は結合されます。[1, 2] と [3, 4] は共通点を持たないため、分かれたままになります。
関数
- startsinteger-array
- 各間隔の開始位置を昇順で
- endsinteger-array
- 各区間の終わりに、開始位置を対応させる
- newStartinteger
- 挿入する区間の開始位置
- newEndinteger
- 挿入する区間の終端
- 戻り値integer-2d-array
- 挿入後の区間を [start, end] のペアとして、start の順に並べます
制約
1 ≤ starts.length == ends.length ≤ 20000 ≤ starts[i] ≤ ends[i] ≤ 105ends[i] < starts[i+1]: 区間は開始位置でソートされており、互いに重なったり接したりするものはありません。0 ≤ newStart ≤ newEnd ≤ 105
例
- 入力
- starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
- 出力
- [[1, 3], [5, 12], [15, 18]]
- 説明
[6, 11]は[5, 7]および[10, 12]と重なるため、3つは[5, 12]になります。[1, 3]は 6 より前に終わり、[15, 18]は 12 より後に始まるため、どちらもそのまま残ります。
- 入力
- starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
- 出力
- [[2, 9]]
- 説明
[4, 8]は 4 で[2, 4]と、8 で[8, 9]と接しているため、3 つすべてが結合して[2, 9]になります。
- 入力
- starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
- 出力
- [[1, 2], [5, 6], [9, 10]]
- 説明
[5, 6]は2と9の間の隙間にあり、どちらの隣とも接していないため、その間に挿入され、何も結合されません。
発展問題
区間を次々にたくさん挿入する場合、各挿入のコストが O(log n) に加えて、統合される既存の区間ごとに1ステップとなるように、どのように格納しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
古い区間はソートされており、すでに互いに重なっていません。新しい区間によって変更される可能性があるのはどれで、それらはリストのどこにあるでしょうか？
区間は3つの連続した範囲に分かれます。
newStartより前に終わるもの、[newStart, newEnd]と重なるか接しているもの、そして統合後の区間の終わりより後に始まるものです。真ん中の範囲は1つの連続したブロックです。リストを一度走査します。区間の終了位置が
newStartより前である間、それらの区間をコピーします。次の区間の開始位置が、構築中の終了位置以前である間、新しい区間を広げてその区間を含めます。新しい区間を追加し、その後、残りをコピーします。
解説
古い区間はソートされていて互いに離れているため、マージを引き起こす可能性があるのは新しい区間だけです。これにより、リストは3つのまとまりに分かれます。新しい区間の開始前に終わる区間、新しい区間と重なるか接している区間、新しい区間の終了後に始まる区間です。最初のまとまりをコピーし、中央のまとまりを1つの区間にまとめ、最後のまとまりをコピーします。1回の走査で済み、ソートは不要です。
それを追加して、すべてをもう一度マージします
考え方
マージ区間の再利用: 新しい区間を追加し、n+1 個の区間をすべて開始位置でソートして、最後にマージした区間を保持しながら順に処理します。ソート後は、区間が重なる可能性があるのは直前のグループだけです。そのため、次の開始位置が保持している終了位置以下なら終了位置を延長し、そうでなければ隙間ができ、新しい区間が始まります。
ソートには、1か所だけ順序が乱れたリストを修正するのに O(n log n) のコストがかかり、元の区間同士はマージされないという点も考慮されていません。
アルゴリズム
- 各開始位置を対応する終了位置と組み合わせ、
[newStart, newEnd]をリストに追加します。 - 開始位置で区間を並べ替えます。
- 順番にたどり、最後に結合した区間を保持します。
- 次の開始位置が保持している終了位置以下の場合、保持している終了位置を2つの終了位置の大きい方に更新します。
- そうでなければ、次の区間を新しい結合区間として追加します。結合したリストを返します。
def insertInterval(starts, ends, newStart, newEnd):
intervals = list(zip(starts, ends))
intervals.append((newStart, newEnd))
intervals.sort()
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # overlaps or touches: stretch
else:
merged.append([start, end]) # a real gap: a new interval begins
return merged3つの部分に分けて1回実行
考え方
リストはソートされ、各区間は互いに離れているため、新しい区間と接する区間は途切れない一続きになります。その一続きより前にあるすべての区間は ends[i] < newStart を満たします。つまり、新しい区間が始まる前に終わります。区間が newStart ちょうどで終わる場合は新しい区間に接しており、マージする必要があるため、この判定には厳密な不等号を使います。
この一続きの中では、starts[i] ≤ mergedEnd を満たす区間は、構築中の区間と重なるか接しているため、開始位置をより小さい方に、終了位置をより大きい方に広げます。mergedEnd より後に始まる最初の区間で一続きは終わります。それ以降の区間はすべて、さらに右から始まるためです。一続きが空の場合、新しい区間は単独で挿入されます。最初の例では、[1, 3] をコピーし、[5, 7] と [10, 12] によって [6, 11] を [5, 12] に広げ、[15, 18] をコピーします。各区間を見るのは一度だけなので、時間計算量は O(n) で、結果以外のメモリは必要ありません。
アルゴリズム
ends[i] < newStartの間、区間を結果にコピーします。mergedStart = newStartおよびmergedEnd = newEndを設定します。starts[i] ≤ mergedEndの間、mergedStartを小さい方の開始位置に、mergedEndを大きい方の終了位置に設定し、次に進みます。[mergedStart, mergedEnd]を追加します。- 残りの区間をコピーし、結果を返します。
def insertInterval(starts, ends, newStart, newEnd):
n = len(starts)
result = []
i = 0
# 1. Intervals that end before the new one starts stay as they are.
while i < n and ends[i] < newStart:
result.append([starts[i], ends[i]])
i += 1
# 2. Intervals that overlap or touch the new one fold into it.
mergedStart, mergedEnd = newStart, newEnd
while i < n and starts[i] <= mergedEnd:
mergedStart = min(mergedStart, starts[i])
mergedEnd = max(mergedEnd, ends[i])
i += 1
result.append([mergedStart, mergedEnd])
# 3. Intervals that start after the merged one ends stay as they are.
while i < n:
result.append([starts[i], ends[i]])
i += 1
return result
落とし穴と境界ケース
- 接する区間に対する不等号を間違える。最初のループで
ends[i] ≤ newStartを使う、または2つ目のループでstarts[i] < mergedEndを使うと、[2, 4]と[4, 8]は分かれたままになります。最初の判定は厳密で、2つ目はそうではありません。 mergedEnd + 1と比較する。これでは、点を共有しない[1, 2]と[3, 4]が結合されます。- 結合後の開始位置として
newStartを保持する。[6, 11]は[5, 7]の途中から始まるため、結果は5から始まります。 - 新しい区間を、何かと重なる場合にしか追加しない。
[5, 6]のように隙間に入る場合や、どちらかの端を越える場合は、中央のループが実行されませんが、それでも追加しなければなりません。 i < nを確認する前にstarts[i]を読み取る。新しい区間が最後の区間より先まで達すると、インデックスが範囲外になります。
よくある質問3
Insert Interval の時間計算量はどれくらいですか？
1回の走査による解法は、各区間をコピーするか、一度だけ折りたたむため、実行時間はO(n)です。また、最大n+1個の区間を含む結果を格納するために、O(n)の空間を使用します。区間を追加して再ソートする場合は、O(n log n)かかります。
Insert IntervalはMerge Intervalsとどう違いますか？
Merge Intervals は、どの区間もほかの区間と重なる可能性がある未ソートのリストから始まるため、まずソートします。ここではリストはソート済みで、既存の区間同士が接することはないため、新しい区間だけがマージを引き起こす可能性があり、それがマージする区間は連続して並びます。1回の走査で十分です。
2つの区間が重なっているかどうかを確認するにはどうすればよいですか？
[a, b] と [c, d] が点を共有するのは、a ≤ d かつ c ≤ b のときです。この問題が求めているように、[2, 4] と [4, 8] のように端点が接する区間も重なっているものとして数えます。端点が接する区間を別々に扱うには、a < d かつ c < b を使います。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def insertInterval(starts, ends, newStart, newEnd):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
starts = [1, 5, 10, 15] ends = [3, 7, 12, 18] newStart = 6 newEnd = 11
期待される出力
[[1, 3], [5, 12], [15, 18]]