Non-overlapping Intervals
区間のリストが2つの配列として与えられます。区間 i は starts[i] から ends[i] までです。残った区間同士が重ならないように、できるだけ少ない数の区間を削除してください。一方の区間が終わる位置ともう一方の区間が始まる位置がちょうど同じで、区間が接しているだけの場合は重なっていません。
削除する必要がある区間の最小数を返す、eraseOverlapIntervals という名前の関数を書いてください。
関数
- startsinteger-array
- 各区間の開始
- endsinteger-array
- 各区間の終了位置。開始位置と同じインデックスにあります
- 戻り値integer
- 残りの区間が重複しないように削除する区間の最小数
制約
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- 区間はソートされていません。2つの区間が同一の場合があります。
例
- 入力
- starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
- 出力
- 2
- 説明
- 開始時刻の順では、区間は [1,4]、[2,3]、[3,6]、[5,7] です。接しているだけの [2,3] と [3,6] を残し、ほかの2つを削除します。3つ残すことはできません。[1,4] は [2,3] と重なり、[3,6] は [5,7] と重なります。また、4つのうちどの3つを選んでも、これらのペアのいずれかを含みます。
- 入力
- starts = [0, 0, 0]ends = [5, 5, 5]
- 出力
- 2
- 説明
- 3つの区間はすべて [0,5] なので、どの2つを選んでも重なります。残せるのは1つだけなので、残りの
2つを削除します。
- 入力
- starts = [4, 1, 2]ends = [6, 2, 4]
- 出力
- 0
- 説明
- [1,2]、[2,4]、[4,6] は端と端が接しており、重なっていないので、何も削除せず、答えは
0です。
提出時に隠しテスト+17件
発展問題
各区間に値も設定されていて、重複しない区間の値の合計を最大にしたいとします。最も早く終了する区間を残す方法は、依然として有効でしょうか？代わりにどのような方法を使いますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
何を削除するかではなく、何を残すかを考えてみましょう。残せる区間の最大の集合は、答えとどのように関係しているでしょうか？
すべての区間の中で、最も早く終わる区間が、残りの区間のために最も多くの余地を残します。最適な答えには、常にその区間が含まれます。
区間を終了位置でソートし、最後に残した区間の終了位置を記憶しながら順に見ていきます。その終了位置以降に開始する区間は残し、それ以外の区間は削除対象として数えます。
解説
削除する区間を最小限にすることは、重ならない区間をできるだけ多く残すことと同じなので、答えは n からその最大集合の要素数を引いたものです。残す区間のあらゆる組み合わせを試すと指数時間がかかり、区間の連鎖に対する動的計画法を使えば O(n²) まで抑えられます。貪欲法のルールを1つ使えば、O(n log n) で解けます。まだ選べる区間のうち、終了時刻が最も早いものを常に選びます。
各区間を残すか削除するか
正しいが、最大のテストでは終わらない
考え方
考え方を逆にしてみましょう。削除する区間を最小限にするということは、重ならない区間をできるだけ多く残すということです。答えは n からその個数を引いた値です。そこで、残せる区間の最大数を探します。
区間を開始位置でソートし、その順番でそれぞれ削除するか残すかを決めます。残せるのは、直前に残した区間の終了位置以降に開始する場合だけです。この条件を確認すれば十分です。残した区間はそれぞれが直前の区間の終了位置以降に始まるつながりになるため、どの2つも重なりません。各区間で両方の選択肢を試し、より良い結果を選びます。
最初の例では、ソート後の区間は [1,4]、[2,3]、[3,6]、[5,7] です。[1,4] を残すと、4より前に始まる [2,3] と [3,6] は残せませんが、[5,7] を残せるので、残せる区間は2つです。[1,4] を削除し、[2,3] を残してから [3,6] も残す場合も、2つ残せます。どの分岐でも3つにはならないため、削除するのは 4-2 = 2 です。
区間ごとに分岐の数が2倍になる可能性があるため、区間が n 個あると、経路は最大で 2^n 個になります。重ならない区間が30個あるだけでも、呼び出し回数は10億回を超えます。また、テストでは最大5000個の区間が与えられます。再帰の深さも n 段階になります。つまり、最大サイズのテストでは5000回の呼び出しとなり、Pythonのデフォルトの上限である1,000を超えます。
アルゴリズム
- 各区間の開始位置と終了位置の対応を保ちながら、開始位置で区間を並べ替えます。
mostKept(i, last)を定義します。lastが最後に保持した区間の位置（該当する区間がない場合は-1）のとき、位置i以降で保持できる区間の最大数です。- リストの末尾を過ぎたら、
0を返します。それ以外の場合は、区間iを削除した結果であるmostKept(i+1, last)から始めます。 - 区間
iの開始位置が区間lastの終了位置以降である場合は、1 + mostKept(i+1, i)も試し、より大きい結果を保持します。 nからmostKept(0, -1)を引いた値を返します。
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
def most_kept(i, last):
# The most intervals you can keep among i..n-1, when interval last
# is the latest one kept so far (-1: nothing kept yet).
if i == n:
return 0
best = most_kept(i + 1, last) # remove interval i
if last == -1 or intervals[i][0] >= intervals[last][1]:
best = max(best, 1 + most_kept(i + 1, i)) # keep interval i
return best
return n - most_kept(0, -1)動的計画法による最長の連鎖
正しいが、最大のテストでは終わらない
考え方
上記の探索では、同じ問いを何度も繰り返し答えています。この区間で終わる最長の連鎖は何か、という問いです。各区間について、その答えを一度だけ保存します。開始位置でソートし、chain[i]を、区間iを最後に残す区間としたときに残せる区間の最大数とします。
iの直前に残す区間は、starts[i]以前に終わっている必要があります。そのような区間はすべてソート順で先に現れます。区間は開始してから終了するため、その開始位置はstarts[i]より前だからです。したがって、ends[j] ≤ starts[i]を満たす最適な先行区間jがある場合はchain[i] = 1 + chain[j]となり、当てはまる区間がない場合は1となります。chainの最大値が残せる区間の最大数です。
最初の例では、[1,4]、[2,3]、[3,6]、[5,7]の順にソートすると、値は1、1、2、2になります。[3,6]は[2,3]の後に続けられ、[5,7]は[1,4]または[2,3]の後に続けられます。最長の連鎖は2なので、4-2 = 2個を削除します。
各区間について、それより前にあるすべての区間を調べるため、チェック回数はn(n-1)/2です。n = 5000の場合、約1250万回のチェックになります。コンパイル言語なら問題ありませんが、最大規模のテストでは遅い言語だと遅すぎ、以下の貪欲法には大きく劣ります。
アルゴリズム
- 各区間の開始位置でソートし、それぞれの開始位置を対応する終了位置と一緒に保持します。
- すべての区間について、
chain[i] = 1に設定します。 - 各
iについて、ends[j] ≤ starts[i]を満たす各j < iに対し、chain[j]+1のほうが大きければ、chain[i]をその値に設定します。 chain内の最大値をnから引いた値を返します。
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
# chain[i]: the most intervals you can keep when interval i is the last one kept
chain = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
chain[i] = chain[j] + 1
return n - max(chain)貪欲法：最も早く終了する区間を残す
考え方
終了位置が最も小さい区間を見てみましょう。最適な解では、必ずそれを選びます。選べる区間の最大の集合を1つ取り、その中で最も早い区間をこれに置き換えます。新しい区間の終了位置は置き換えた区間の終了位置より後にならないため、次に選んだ区間の開始位置以前に終了します。集合は重複のない状態を保ち、サイズも変わらないので、終了位置が最も早い区間を選んでも損はありません。
それを選んだら、その終了位置より前に始まる区間はすべて重複するため、取り除く必要があります。残った区間について同じ問題を解けばよいので、同じルールを繰り返し適用します。実際には、終了位置でソートしてリストを順に見ていき、最後に選んだ区間の終了位置であるlastEndを記録します。開始位置がlastEnd以上の区間を選び、それ以外の区間は取り除いたものとして数えます。
最初の例を終了位置でソートすると、[2,3]、[1,4]、[3,6]、[5,7]となります。[2,3]を選ぶので、lastEnd = 3です。[1,4]の開始位置は1で、3より前なので、取り除きます。[3,6]の開始位置は3で、3より前ではないので、選び、lastEnd = 6とします。[5,7]の開始位置は5で、6より前なので、取り除きます。取り除いた区間は2つです。
ほかの基準もよさそうに見えますが、うまくいきません。開始位置でソートすると、[1,2]、[3,4]、[5,6]を含む[0,100]を選ぶことになり、1つではなく3つの区間を取り除くことになります。最短の区間を選ぶ方法も、[1,5]、[4,7]、[6,10]ではうまくいきません。短い[4,7]はほかの2つと重複するため、選ぶと、1つ取り除けば済むところを2つ取り除くことになります。終了位置を基準にすれば、その後に続くすべての区間のために、最も多くの余地を残せます。
ソートにO(n log n)、リストの走査にO(n)かかります。区間をソートしたコピーにはO(n)の領域が必要です。
アルゴリズム
- 各区間の終了点と開始点の対応を保ったまま、終了点で区間をソートします。
- 最初の区間を残し、
lastEndにその終了点を、removedに0を設定します。 - 後続の各区間について、開始点が
lastEnd以上ならその区間を残し、lastEndにその終了点を設定します。 - そうでなければ、
removedに1を加えます。 removedを返します。
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(ends, starts)) # by end time
removed = 0
last_end = intervals[0][0] # the interval that ends first is always kept
for end, start in intervals[1:]:
if start >= last_end:
last_end = end # it fits after the last kept interval: keep it
else:
removed += 1 # it overlaps the last kept interval: remove it
return removed
落とし穴と境界ケース
誤答の原因の多くは、ソートキーか、端点が接する場合の比較にあります。
- 端点が接する区間を重なっているものとして扱う。
start > lastEndをstart ≥ lastEndの代わりに使うと、[1,2]、[2,4]、[4,6]の連なりでは、[1,2]の終点とちょうど同じ位置から始まる[2,4]が削除され、答えは0ではなく1になります。 - 開始位置でソートし、重なった場合に常に先にある区間を残す。[0,100]のような幅の広い区間は、その後に続く[1,2]、[3,4]、[5,6]を押し出してしまいます。開始位置でソートする場合は、重なっている2つの区間のうち、終点が早い方を残してください。
- ソート済みリストの隣り合う区間と比較し、最後に残した区間と比較しない。[1,4]を削除した後、次の区間は4ではなく、[2,3]の終点と比較する必要があります。
startsとendsを別々のリストとしてソートする。それぞれの終点は対応する始点と組にしておく必要があります。そうしないと、ある区間の始点を別の区間の終点と比較することになります。- 残した区間の数を返す。問題で求められているのは削除した区間の数であり、これは
nから残した区間数を引いた数です。
よくある質問4
重複しない区間の時間計算量はどのくらいですか？
貪欲法では、区間を終了位置でソートするのに O(n log n) かかり、その後 O(n) で一度走査するため、全体では O(n log n) です。区間をソートしたコピーには O(n) の領域を使います。動的計画法の方法は O(n²) で、保持する集合をすべて試す方法は O(2^n) です。
なぜ終了時刻でソートすると、削除数が最小になるのでしょうか？
最初に終了する区間は、それより後に終了することはないため、重なりを作らずに最適解の最初の区間と置き換えられます。したがって、最適解の中にはこの区間を採用するものがあり、これと重なる区間をすべて取り除いた後に残る部分は、より小さな集合に対する同じ問題です。この議論を繰り返すと、貪欲法によるすべての選択が安全であることがわかります。
代わりに開始時刻でソートできますか？
はい、重複に関するルールが異なります。開始時刻で区間を順に見ていき、次の区間が最後に残した区間と重なる場合は、1つ削除したと数え、2つのうち先に終わる方を残します。終了時刻でソートする方法と同じ数の区間を削除でき、実行時間も同じく O(n log n) です。
重なりのない区間は、活動選択問題と同じですか？
これはその反対側です。アクティビティ選択では重複しない区間をできるだけ多く選ぶのに対し、この問題では削除する区間をできるだけ少なくします。その数は n から選んだ区間数を引いたものです。同じ貪欲法のルール、つまり最も早く終了するアクティビティを残す方法で、どちらの問題も解けます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def eraseOverlapIntervals(starts, ends):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
期待値
2