Insert Interval
開始位置でソートされた区間のリストが、同じ長さの2つの配列として与えられます。区間 i は [starts[i], ends[i]] です。どの2つの区間も重なったり接したりしていません。さらに、新しい区間 [newStart, newEnd] が1つ与えられます。これを挿入し、重なるか接するすべての区間と結合して、すべての区間を開始位置でソートされた [start, end] のペアの2次元配列として返してください。
一方の区間の終点がもう一方の始点と同じ場合、2つの区間は接しています。たとえば [2, 4] と [4, 8] は接しており、接している区間は1つに結合されます。[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]：区間は開始位置でソートされており、どの2つの区間も重なったり接したりしていません。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の間の隙間にあり、どちらの隣とも接していないため、その間に挿入され、何も結合されません。
提出時に隠しテスト+20件
発展問題
同じリストに新しい区間を次々と挿入するとします。挿入のコストが O(log n) に加えて、重なる古い区間ごとに1ステップで済むようにするには、区間をどのように格納しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
古い区間はソート済みで、すでに互いに重なっていません。新しい区間によって変更される可能性があるのはどの区間で、それらはリストのどこにありますか？
区間は3つの連続したまとまりに分かれます。
newStartより前に終わるもの、[newStart, newEnd]と重なるか接しているもの、結合後の区間の終わりより後に始まるものです。中央のまとまりはひと続きのブロックです。リストを1回走査します。
newStartより前に終わる区間をコピーします。次に、次の区間が作成中の終端以前に始まる間、新しい区間を広げてその区間を含めます。新しい区間を追加し、その後、残りをコピーします。
解説
既存の区間はすでに互いに離れて順番に並んでいるため、結合の原因になりうるのは新しい区間だけです。これにより、リストは3つのまとまりに分けられます。新しい区間が始まる前に終わる区間、新しい区間と重なるか接する区間、新しい区間が終わった後に始まる区間です。最初のまとまりをコピーし、中央のまとまりを1つの区間にまとめ、最後のまとまりをコピーします。1回の走査で済み、ソートは不要です。
それを追加して、すべてをもう一度マージする
考え方
Merge Intervalsを解いたことがあれば、その解法をここで再利用できます。新しい区間をリストに加え、n+1個の区間を開始位置でソートしてからマージします。ソート後、ある区間が重なる可能性があるのは直前のグループだけなので、最後にマージした区間を保持しながらリストを順に見ていきます。次の区間の開始位置がその終了位置以下なら、終了位置を広げます。そうでなければ実際に隙間があるので、新しい区間が始まります。
最初の例で実行してみましょう。リストは[1, 3]、[5, 7]、[6, 11]、[10, 12]、[15, 18]になります。5は3より大きいため、[1, 3]は単独のままです。6は7以下なので、[5, 7]は[5, 11]に広がります。10は11以下なので、[5, 12]に広がります。15は12より大きいため、[15, 18]が新しい区間として始まります。
この方法は正しく、区間が2000個あっても高速に実行できます。しかし、与えられた2つの事実、つまりリストはすでにソートされていることと、既存の区間同士は決してマージされないことを活用できていません。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回のパス
考え方
インデックス i を使ってリストを一度走査し、3つの区間に分けます。まず、ends[i] < newStart を満たす区間はすべて、新しい区間が始まる前に終わるため、新しい区間とは点を共有しません。結果にコピーします。新しい区間とちょうど newStart で終わる区間は接しており、結合する必要があるため、判定には厳密な < を使います。
次に、starts[i] ≤ mergedEnd を満たす区間はすべて、作成中の区間と重なるか接しています。これらを取り込みます。mergedStart は開始位置の小さい方に、mergedEnd は終了位置の大きい方になります。この区間群に含まれる区間は、リストがソートされているため、互いに隣り合っています。ある区間の開始位置が mergedEnd より後になれば、その後の区間はすべてさらに右から始まるため、それ以降に結合できる区間はありません。結合した区間を追加します。この処理では、区間群が空で、新しい区間を単独で追加する場合も扱います。
3つ目に、残りのすべてをコピーします。これらの区間は結合した区間の終わりより後から始まり、もともと互いに離れています。
最初の例をたどってみましょう。[1, 3] は6より前に終わるため、コピーします。[5, 7] は5から始まり、5は11以下なので、結合後の区間は [5, 11] になります。[10, 12] は10から始まり、10は11以下なので、[5, 12] になります。[15, 18] は12より後から始まるため、[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番目の条件はそうしません。 - 隣接しているように見えるだけの区間を結合する。
[1, 2]と[3, 4]は点を共有しないため、mergedEnd + 1と比較すると、別々のままにすべき区間が結合されます。 newStartを結合後の開始位置としてそのまま使う。新しい区間が既存の区間の途中から始まる場合、たとえば[6, 11]が[5, 7]の中から始まる場合、結果の開始位置は 5 です。2つの開始位置のうち小さい方を使いましょう。- 新しい区間が何かと重なる場合にだけ追加する。すべての区間より前、すべての区間より後、または隙間に入る場合、中間のループは実行されません。それでも新しい区間を追加する必要があります。
i < nを確認する前にstarts[i]またはends[i]を読み取る。新しい区間が最後の区間を越える場合、インデックスが配列の範囲外になります。
よくある質問4
Insert Interval の時間計算量はどのくらいですか？
1回の走査による解法の実行時間は O(n) です。各区間は、コピーされるか統合されるかのいずれかを1回だけ行います。結果には最大 n+1 個の区間が含まれるため、必要な空間は O(n) であり、入力に応じて増えるものはほかにありません。区間を追加して再ソートする方法では、代わりに O(n log n) かかります。
Insert IntervalはMerge Intervalsとどう違いますか？
Merge Intervals は、どの区間もほかの区間と重なる可能性がある未ソートのリストから始まるため、まずソートする必要があります。Insert Interval ではリストはすでにソートされており、既存の区間同士が重なることはないため、新しい区間だけがマージを引き起こす可能性があります。マージされる区間は途切れずに連続しているため、ソートせずに1回走査するだけで十分です。
2つの区間が重なっているかどうかは、どうすれば確認できますか？
区間 [a, b] と [c, d] が少なくとも1つの点を共有するのは、a ≤ d かつ c ≤ b のときです。これにより、[2, 4] と [4, 8] のように端点で接する区間も重なっているものとして数えます。この問題で求められているのはその扱いです。端点で接する区間を別々に扱う必要がある場合は、代わりに a < d かつ c < b を使います。
二分探索を使えば、区間挿入を高速化できますか？
二分探索では、開始位置と終了位置がどちらもソートされているため、マージ後の区間の開始位置と終了位置をO(log n)で見つけられます。ただし、この関数は新しいリストを返すため、変更されない区間をそこにコピーするコストはO(n)です。そのため、全体の計算量は引き続きO(n)です。二分探索の効果が得られるのは、平衡木のように、コピーせずに範囲を削除・挿入できるデータ構造に区間が格納されている場合です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
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]]