概要

直線状に並んだ \(N\) 個の区画すべてをカバーするために、与えられた区間（警備員候補）の中から最小個数を選ぶ区間被覆問題（Interval Covering Problem）です。

考察

重要な気づき

この問題は「数直線上の区間 \([1, N]\) を、与えられた複数の区間で完全に覆うとき、最小何個の区間が必要か？」という古典的な貪欲法の問題です。

素朴なアプローチの問題点

すべての警備員の選び方を全探索すると \(2^M\) 通りあり、\(M\) が最大 \(2 \times 10^5\) なので到底間に合いません。

貪欲法による解決

区間被覆問題には、以下の貪欲戦略が最適解を与えることが知られています：

まだカバーできていない最も左の位置をカバーできる区間のうち、右端が最も大きいものを選ぶ。

具体例で考えてみましょう。\(N = 10\) で区間が \([1,3], [2,6], [4,8], [7,10]\) の場合：

1. まずカバー済み = \(0\)。位置 \(1\) をカバーしたい → \(L \leq 1\) の区間は \([1,3]\) と \([2,6]\)（\([2,6]\) は \(L=2 > 1\) なので対象外）。\([1,3]\) を選び、カバー済み = \(3\)。
2. 位置 \(4\) をカバーしたい → \(L \leq 4\) の区間で \(R\) 最大は \([4,8]\)（\(R=8\)）と \([2,6]\)（\(R=6\)）。\([4,8]\) を選び、カバー済み = \(8\)。
3. 位置 \(9\) をカバーしたい → \(L \leq 9\) の区間で \([7,10]\)（\(R=10\)）を選び、カバー済み = \(10\)。

答えは \(3\) 人です。

アルゴリズム

1. 区間を左端 \(L_i\) の昇順にソートする。
2. 変数 covered（カバー済みの右端、初期値 \(0\)）と、区間を走査するポインタ i を用意する。
3. covered < N の間、以下を繰り返す：
   • 次にカバーすべき位置は covered + 1。
   • \(L \leq\) covered + 1 を満たす区間を順に見て、その中で \(R\) が最大のものを best として記録する。
   • best が見つからない（または best \(\leq\) covered）なら、カバー不可能なので \(-1\) を出力。
   • そうでなければ covered = best とし、選んだ警備員数を \(1\) 増やす。
4. ループ終了後、選んだ警備員数を出力する。

ポイント: ソート済みの区間を前から順に見ていくため、ポインタ i は戻ることがなく、全体で各区間を高々 \(1\) 回ずつしか見ません。

計算量

• 時間計算量: \(O(M \log M)\)（ソートが支配的。貪欲法のループ自体は \(O(M)\)）
• 空間計算量: \(O(M)\)（区間を格納する配列）

\(N\) が最大 \(10^9\) と非常に大きいですが、ループは区間の数 \(M\) に依存するため問題ありません。

実装のポイント

• covered は「区画 \(1\) ～ covered がカバー済み」を意味し、初期値 \(0\)（何もカバーしていない状態）とする。次にカバーすべき位置は covered + 1。

• ソート後にポインタ i を使って区間を一度だけ走査する（尺取り法的なテクニック）ことで、ループ全体を \(O(M)\) に抑えている。

• カバーを延長できない場合（best == -1 または best <= covered）は不可能と判定して早期に \(-1\) を返す。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    intervals = []
    for i in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        intervals.append((L, R))
    
    # Greedy interval covering
    # Sort by left endpoint
    intervals.sort()
    
    count = 0
    covered = 0  # we have covered up to 'covered' (0 means nothing covered yet)
    i = 0
    
    while covered < N:
        # We need to cover position covered+1
        # Find the interval with L <= covered+1 that has the maximum R
        best = -1
        while i < M and intervals[i][0] <= covered + 1:
            if intervals[i][1] > best:
                best = intervals[i][1]
            i += 1
        
        if best == -1 or best <= covered:
            # Can't extend coverage
            print(-1)
            return
        
        covered = best
        count += 1
    
    print(count)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。