0Pricing
Coding Interview Prep · レッスン

重複をなくすための最小削除数

終了時刻が早いものを貪欲に残してスケジュールします

「重複をなくすための最小削除数」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

削除の目標

重複する区間があり、重複がなくなるように最小限の削除を行いたいとします。できるだけ多くの区間を残します。✂️

問題を反転する

最小限の削除は、重複しない区間を最大限残すことと同じです。残す場合の問題を解けば、削除数は n から残した数を引いた値になります。

これはアクティビティ選択です

重複しない区間を最大限残す問題は、古典的なアクティビティ選択問題を別の形で表したものです。同じ貪欲法の考え方で、どちらも解けます。

終了時刻でソートする

ここで有効な順序は、開始時刻ではなく終了時刻です。早く終了する区間を選ぶほど、次に残せる区間のためにタイムラインを早く空けられます。

intervals.sort(key=lambda x: x[1])

貪欲な選択

まだ両立可能な区間の中から、最も早く終了する区間を常に残します。そうすれば、残りの区間のために最大限の余地を残せます。

最後に残した区間の終了位置を記録する

最後に残した区間の終了位置を保持します。次の区間は、その開始位置が境界以上の場合にのみ両立します。

if start >= last_end:
    last_end = end

削除数を数える

区間の開始位置が last_end より前なら競合するため、その区間を破棄して削除数を 1 増やします。それ以外の場合は残します。

else:
    removed += 1

最も早い終了が有利な理由

交換論法で証明できます。残している区間を、両立する中で最も早く終了する区間に置き換えても、残せる区間数は決して減りません。

接触する場合を扱う

[1, 2] と [2, 3] を重複として数えるか決めます。端点を共有するだけなら許可される場合は、判定に start >= last_end を使います。

貪欲法の全体像

終了時刻でソートし、一度スイープして競合数を数えます。全体の計算量は、ソートの O(n log n) と 1 回の線形走査を合わせたものです。

removed = 0; last_end = float('-inf')
for s, e in intervals:
    if s >= last_end: last_end = e
    else: removed += 1

おなじみの形

このパターンは、1 つの部屋で開催できる会議数を最大化したり、1 台の機械で処理できる仕事数を最大化したりする場合に使われます。競合を最小化する必要があるときは、この形に気づいてください。

確認

重複しない区間を貪欲に残します。

まとめ

最小削除数は、n から残せる区間の最大数を引いた値です。終了時刻でソートし、最も早く終了する両立可能な区間を貪欲に残して、残りを数えます。🚀

よくある質問

「重複をなくすための最小削除数」レッスンは無料ですか？

はい。「重複をなくすための最小削除数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「重複をなくすための最小削除数」で何を学びますか？

終了時刻が早いものを貪欲に残してスケジュールします ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「重複をなくすための最小削除数」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 開始位置で区間をソートする
  2. 重なり合う区間をマージする
  3. 最大重複数を求めるラインスイープ
  4. 重複をなくすための最小削除数
← Coding Interview Prepに戻る