区間問題の解き方｜「左端ソート」と「右端ソート」の使い分けのコツ

Aru

区間 [l, r] を扱う問題において、左端 l と右端 r のどちらでソートすれば良いか悩むことがあります。これは、何を求める問題なのかである程度決まります。この記事ではそれぞれについて代表的な例題を使いながら解説します。

Contents

区間問題とは
左端ソートで解く問題
- 例：重複する区間があるかどうかを調べる問題
- 例：重複区間を結合する問題
右端ソートで解く問題
- 例：区間スケジューリング問題 (Interval Scheduling)
まとめ

区間問題とは

アルゴリズムやプログラミングの問題では、「開始時間と終了時間」や「数直線上の始点と終点」など、２つの値のペア $(l, r)$ で表される「区間」を扱う問題が頻出します。

「重なっている会議室の予約をまとめたい」
「限られた時間の中で、できるだけ多くのタスクをこなしたい」

このような問題を解くために強力なのが「ソート」です。しかし、区間には $l$（左端・開始）と $r$（右端・終了）の２つの基準があるため、「どちらを基準にソートすればいいの？」と迷ってしまうことがよくあります。

結論から言うと、「左から右へ順に状態を見ていくなら左端ソート」、「出来るだけ多く選びたい（貪欲法）なら右端ソート」が基本戦略になります。それぞれの具体的な問題と解法を見ていきましょう。

結論

左から右へ順に状態を見ていくなら左端（L）ソート
出来るだけ多く選びたい（貪欲法）なら右端（R）ソート

競技プログラミングやプログラミング問題では、右端ソートの方が出題率が高い気がします。

左端ソートで解く問題

左端（開始地点）でソートするアプローチは、「時間軸（数直線）を左から右へ順番に走査（スキャン）していく」場合に有効です。たとえば、現在見ている区間と、次にやってくる区間の「重なり具合」を判定する場合などに有効です。

例：重複する区間があるかどうかを調べる問題

「与えられた予定の中に、時間が被っているものがあるか？」を判定するシンプルな問題です。

解法

左端でソートすると、リストの中で隣り合う区間同士だけを比較すれば良くなります。「前の区間の終了時間」よりも「次の区間の開始時間」が早ければ、その２つは重なっていると判断できます。

def has_overlap(a):
    """
    重複する区間が存在するかどうかを判定する
    a: [[l1, r1], [l2, r2], ...] のリスト
    """    
    a.sort(key=lambda x: x[0])
    for i in range(1, len(a)) :
        if a[i][0] < a[i-1][1]:
            return True
    return False



a = [[1, 3], [5, 7], [2, 4]]
print(f"予定 {a} の重複: {has_overlap(a)}") # True (1-3 と 2-4 が被る)

b = [[1, 3], [7, 9], [4, 6]]
print(f"予定 {b} の重複: {has_overlap(b)}") # False

プログラムの説明

a = [[1, 3]...]は、a[i][0]が左端$l$、a[i][1]が右端$r$になります。has_overlap関数では、第一要素（左端）でソートし、i-1の右端とiの左端が重なっていれば（同じは許可）、重なりがあるとしてTrueを返します。

例：重複区間を結合する問題

「重なり合っている区間をすべて一つにまとめ（マージし）、互いに独立した区間のリストを作る」問題です。区間を結合することで、重複をなくす処理になります。

解法

これも左端でソートします。結果を保存するリストを用意し、順番に区間を見ていきます。重なっていれば「終了時間」を更新して区間を伸ばし、重なっていなければ新しい区間としてリストに追加します。

def merge_intervals(a):
    """
    重複する区間を結合して返す
    """
    a.sort(key=lambda x: x[0])
    
    result = [a[0]]
    
    for current in a[1:]:
        last = result[-1]
        
        # 重なっている場合（現在の開始 <= 最後の終了）
        if current[0] <= last[1]:
            # 終了時間を、より遅い方に更新（区間を延長）
            last[1] = max(last[1], current[1])
        else:
            # 重なっていない場合、新しい区間として追加
            result.append(current)
            
    return result

x = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(f"結合前: {x}")
print(f"結合後: {merge_intervals(x)}") # [[1, 6], [8, 10], [15, 18]]

プログラムの説明

resultにマージした区間が入ります。最後の区間と現在の区間を比べて、重なりがある場合は末尾を更新し、重なりがなければ追加します。

このほか、「区間被覆問題」と言われる。区間全体をカバーする最小の個数を求める問題も、左端ソートで解くことができます。

右端ソートで解く問題

右端（終了地点）でソートするアプローチは、「できるだけ多くの区間を選びたい」という貪欲法（Greedy Algorithm）で利用します。

例：区間スケジューリング問題 (Interval Scheduling)

この問題として有名なのは、「1つの会議室しかありません。複数の会議の予定（開始と終了）が与えられたとき、最大でいくつの会議を開催できますか？」という超定番問題です。

解法

「短い会議から選ぶ」「早く始まる会議から選ぶ」など色々な戦略を思いつきますが、正解は「終わるのが早い会議から優先して選ぶ（右端ソート）」です。早く終わる会議を選べば、その後ろにより多くの「空き時間」を残すことができるため、結果的に最も多くの会議を詰め込むことができます。

なぜ「終わるのが早い順」が正解なのか？（他の戦略がダメな理由）

一見すると他の選び方でも良さそうに思えますが、以下のような場合によくない選択となります。

「早く始まる順（左端ソート）」
朝一番に始まる会議でも、それが夕方までかかる超ロング会議だったら、その日はもう他の会議を一つも入れられなくなってしまいます。
「短い順」
15分だけの短い会議でも、それが他の2つの重要な会議のちょうど間の時間を跨いでしまっている場合、短い会議を1つ選んだせいで、本来ならできたはずの2つの会議を両方とも諦めなければならなくなります。

結局、「今の時点で最も早く終わる会議」を選ぶことが、正解となります。最も早く終わる会議を選ぶということは、言い換えると、残りの空き時間を最も長く保つ（＝未来の選択肢を一番多く残す）ことになるからです。

def interval_scheduling(a):
    """
    開催できる会議の最大数を返す（区間スケジューリング）
    """
    # 右端 (インデックス1) を基準に昇順ソート
    # 終わるのが早い順に並べる
    a.sort(key=lambda x: x[1])
    
    cnt = 0
    cur = -float('inf')
    
    # 終わるのが早い順に会議を見ていく
    for start, end in a:
        # 前の会議が終わった後に始まる会議なら、採用する
        if start >= cur:
            cnt += 1
            cur = end # 会議室が空く時間を更新
            
    return cnt

meetings = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]
print(f"最大開催数: {interval_scheduling(meetings)}") # 4つ (例: [1,4], [5,7], [8,11], [12,16])