0Pricing
Competitive Programming Academy · レッスン

重なり合う区間をマージする

接触または重複する範囲を結合します

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

マージの目的

複数の区間が与えられたら、接している区間や重なっている区間をマージし、重ならない範囲の数をできるだけ少なくします。🧩

2 つの区間が重なる場合

一方の区間がもう一方の区間の終了より前に始まるとき、2 つの区間は重なります。開始値でソートした後なら、次の開始値が現在の終了値以下であることを意味します。

必ず最初にソートする

区間が順序どおりでなければ左から右へのマージはできないため、まず開始値でソートします。これが走査全体の基礎になります。

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

現在の範囲を保持する

ソート済みのリストを走査しながら、マージ中の現在の区間を 1 つ保持します。新しい区間は、それを拡張するか、新しい範囲を開始するかのどちらかです。

重なったら拡張する

次の開始値が現在の範囲内にある場合は重なっているため、2 つの終了値のうち大きい方まで現在の終了値を伸ばします。

cur_end = max(cur_end, end)

終了値の最大値を取る

新しい終了値には必ずmaxを使います。長い区間の内側にある短い区間によって、すでに作った範囲を縮めてはいけません。

閉じて新しい範囲を開く

次の開始値が現在の終了値より後ろにある場合は、空きがあります。完成した範囲を答えに追加し、新しい現在の区間を開始します。

result.append([cur_start, cur_end])

最後の区間を忘れない

ループでは最後の範囲を作るだけで、追加までは行いません。ループ終了後に、最後の現在の区間をappendして失わないようにしてください。

接触も重複に含める

[1, 3] と [3, 5] を結合するべきか判断します。通常は結合するため、start <= cur_end を使います。この端の扱いが正しいか、問題文を読んで確認してください。

一度のスイープ

ソート後に一度走査するだけで、結合済みの範囲をすべて得られます。そのため、全体の計算量はソートの O(n log n) と線形スイープを合わせたものになります。

for s, e in intervals[1:]:
    if s <= cur_end:
        cur_end = max(cur_end, e)
    else:
        result.append([cur_start, cur_end]); cur_start, cur_end = s, e

よくある用途

カレンダーや予約システムを強化するのが区間の結合です。予定の入っているブロックをまとめると、実際の空き時間を確認できます。多くのコンテスト問題にも、同じ形が隠れています。

確認

開始位置でソートした後に、区間を結合します。

まとめ

開始位置でソートし、現在の範囲を保持します。重複していれば max で拡張し、隙間があれば追加して新しい範囲に切り替えます。最後の追加を忘れないでください。🚀

よくある質問

「重なり合う区間をマージする」レッスンは無料ですか？

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

「重なり合う区間をマージする」で何を学びますか？

接触または重複する範囲を結合します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

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

「重なり合う区間をマージする」レッスンにはどのくらい時間がかかりますか？

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

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

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

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

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