Non-overlapping Intervals
区間 i は starts[i] から ends[i] までです。残りの区間同士が重ならないように、削除する必要がある区間の最小数を返してください。一方の区間が終わる点ともう一方の区間が始まる点が一致するだけの、互いに接している区間は重なりません。
関数
- 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] と重なるためです。
- 入力
- 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です。
発展問題
各区間に値があり、重複しない区間の中で合計値を最大にしたいとします。最も早く終了する区間を選ぶ方法は、引き続き有効でしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
何を削除するかを選ぶのではなく、何を残すかを考えてみましょう。残せる区間の最大数は、答えとどのように関係していますか？
すべての区間の中で、最初に終わる区間が、残りのために最も多くの余地を残します。最適な答えには、必ずその区間が含まれます。
区間を終了位置でソートし、最後に残した区間の終了位置を記憶しながら順に見ていきます。その終了位置以降に始まる区間は残し、それ以外の区間は削除されたものとして数えます。
解説
削除する区間を最小限にすることは、重ならない区間をできるだけ多く残すことと同じです。答えは、n からその個数を引いた値です。貪欲法のルールを1つ使えば、O(n log n) で個数を求められます。まだ選べる区間のうち、常に終了時刻が最も早いものを選びます。
各区間を保持するか削除する
正しいが、最大のテストでは終わらない
考え方
区間を開始位置でソートし、それぞれについて残すか削除するかを決めます。残せるのは、直前に残した区間の終了位置以降に開始する場合だけです。これにより、残した区間は重複のない一連の区間になります。各区間で両方の選択肢を試し、より大きい個数を選びます。答えはnからその個数を引いた値です。
区間ごとに分岐が倍増するため、n個の区間では最大で2^n通りの経路が生じます。重複しない区間が30個あるだけでも、呼び出し回数は10億回を超えます。また、nは最大5000です。
アルゴリズム
- 各開始位置を対応する終了位置と組にしたまま、区間を開始位置でソートします。
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]以前に終わるため、開始時刻がより早く、ソート順でも前にあります。したがって、条件を満たす最適なjがあればchain[i] = 1 + chain[j]、なければ1となります。最初の例では値は1、1、2、2となるため、2つ残して2つ削除します。
二重ループではn(n-1)/2回チェックします。n = 5000の場合、約1,250万回です。
アルゴリズム
- 各区間の開始位置でソートし、それぞれの開始位置と終了位置の組み合わせを保ちます。
- すべての区間について、
chain[i] = 1に設定します。 - 各
iと、ends[j] ≤ starts[i]を満たす各j < iについて、より大きい場合はchain[i]をchain[j]+1に設定します。 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)貪欲法：終了時刻が最も早い区間を選ぶ
考え方
終点が最も小さい区間を選びます。最適解の一つにもその区間が含まれています。選べる区間の数が最大の集合では、最初に選んだ区間をこの区間に入れ替えられます。この区間の終点はそれ以前に選んだ区間の終点より後にならないため、次に選んだ区間の始点以前に終わり、重複のないまま集合のサイズを保てます。終点より前に始まる区間はすべてこの区間と重なるため取り除く必要があり、残るのはその終点以降に始まる区間についての同じ問題です。
最初の例では、終点でソートすると、[2,3]を残し、[1,4]を取り除き、[3,6]を残し、[5,7]を取り除きます。代わりに最も短い区間を残す方法は、[1,5]、[4,7]、[6,10]の場合にはうまくいきません。[4,7]は他の2つの区間と重なり、1つ取り除けば十分なところを2つ取り除くことになります。
ソートにはO(n log 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] の連鎖では、0 ではなく 1 になります。 - 開始位置でソートし、重複時に先にある区間を残す。幅の広い [0,100] が [1,2]、[3,4]、[5,6] を押し出すため、削除数は1ではなく3になります。
- ソート済みリストで各区間を直前の区間と比較し、最後に残した区間とは比較しない。最初の例では、[3,6] は削除された [1,4] ではなく、[2,3] の終端と比較しなければなりません。そうしないと、答えは3になります。
startsとendsを別々のリストとしてソートする。それぞれの終端は、対応する開始位置と一緒にしておく必要があります。- 削除する区間の数ではなく、残す区間の数を返す。
よくある質問3
重複しない区間の時間計算量はどれくらいですか？
貪欲法の解法は終了時刻で O(n log n) の時間でソートし、区間を一度走査するため、合計の計算量は O(n log n) で、ソート済みコピーのために O(n) の領域を使用します。動的計画法のバージョンは O(n²) で、保持する集合をすべて試す方法は O(2^n) です。
代わりに開始時刻で並べ替えられますか？
はい、重なりに関するルールを変えれば可能です。開始位置順に区間を確認し、次の区間が最後に残した区間と重なる場合は、削除を1つとして数え、2つのうち先に終わる方を残します。同じ数を同じ O(n log n) 時間で求められます。
重複しない区間は、活動選択問題と同じですか？
その問題のもう一方です。活動選択問題では、重複しない区間をできるだけ多く選びます。この問題では、削除する区間をできるだけ少なくすることを求めており、その数は n からその個数を引いたものです。同じ貪欲法のルール、つまり終了時刻が最も早い活動を選ぶ方法で、どちらの問題も解けます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def eraseOverlapIntervals(starts, ends):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
期待される出力
2