0Pricing
Coding Interview Prep · レッスン

最大重複数を求めるラインスイープ

イベントを使って同時に存在する区間を数えます

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

最大重複数を求める問い

同じ時点を同時に含む区間はいくつあるでしょうか。ピーク時の数が最大重複数であり、タイムライン上で最も混雑する時点を表します。📈

イベントで考える

区間全体で考えるのをやめましょう。それぞれの区間を 2 つのイベントに分けます。開始時には +1、終了時には -1 を追加します。

イベントリストを作る

すべての区間について、開始イベントと終了イベントを 1 つの共有リストに追加します。各イベントには位置と、プラスまたはマイナス 1 の差分を持たせます。

events = []
for s, e in intervals:
    events.append((s, 1)); events.append((e, -1))

イベントをソートする

すべてのイベントを位置でソートします。そうすれば、タイムラインを左から右へスイープし、変化を正しい順序で処理できます。

events.sort()

スイープして数える

ソート済みのイベントを順に処理しながら、実行中のカウンターを保持します。通過するたびに各差分を加えると、そのカウンターが現在アクティブな区間の数になります。

active = 0
for pos, delta in events:
    active += delta

ピークを記録する

更新するたびに、カウンターとそれまでの最大値を比較します。カウンターが到達した値のうち最も大きいものが最大重複数です。

best = max(best, active)

同じ位置の順位付け

位置が等しい場合は順序が重要です。x で終了する区間が x で開始する区間より先に枠を空けるべきなら、同じ位置では終了イベントを開始イベントより前にソートします。

差分を符号化して正しくソートする

同じ位置での順序を決める便利な方法は、タプルのソートだけで処理できるように差分を選ぶことです。位置が一致したときは、-1 の差分を +1 より前に置きます。

events.append((s, 1)); events.append((e, -1))  # -1 sorts first at a tie

高速な理由

2n 個のイベントを作成し、一度ソートして、一度スイープします。全体の計算量はO(n log n)で、1 回のソートが支配的です。

使われる場面

最大重複数は、会議に必要な最小部屋数や、サーバー上で同時に接続するユーザー数のピークなど、典型的な問題に答えを与えます。

数えるだけではない応用

同じスイープを簡単に拡張できます。カバーされている長さの合計を追跡したり、カウントが変化するすべての位置を見つけたりする処理も、1 回の線形走査で行えます。

確認

イベントをスイープして最大重複数を求めます。

まとめ

区間を +1 の開始イベントと -1 の終了イベントに変換し、ソートしてからカウンターをスイープするとピークを求められます。同じ位置では、開始より終了を先に処理して同順位を解決します。🚀

よくある質問

「最大重複数を求めるラインスイープ」レッスンは無料ですか？

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

「最大重複数を求めるラインスイープ」で何を学びますか？

イベントを使って同時に存在する区間を数えます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「最大重複数を求めるラインスイープ」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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