概要

直線上の区画をカバーする最小の警備員数を求める問題。各区画は連続した範囲をカバーでき、全体をカバーするために選ぶべき警備員の最小数を貪欲法で求めます。

考察

この問題は典型的な「区間スケジューリング問題」の一種であり、「できるだけ広い範囲をカバーする警備員を選ぶ」という貪欲法が有効です。

重要な観察

• 各ステップで、今カバーされている区画の「次の未カバー地点」（つまり covered + 1）をカバーできる警備員の中から、最も遠くまでカバーできるものを選ぶのが最適です。
• これによって、少ない警備員数で広い範囲をカバーできます。

素朴なアプローチでは…

• 全探索などで組み合わせを試すと、指数時間かかります（TLE）。
• また、単純に重複なく区間を選んでも、全体をカバーしきれないことがあります（WA）。

解決策

• 区間を開始位置でソートして順番に見ていき、各ステップで「次にカバーすべき地点」をカバーできる中で最も遠くまで届く区間を選ぶ。
• これにより、最小数の区間で全体をカバーできます。

アルゴリズム

1. すべての区間を開始位置 \(L_i\) で昇順にソートします。
2. covered: 現在カバーされている区画の右端（初期値は 0）。
3. count: 選んだ警備員の数。
4. covered < N の間、以下を繰り返します：
   • 開始位置が covered + 1 以下であるような区間のうち、右端が最大のものを選びます。
   • そのような区間が存在しなければ -1 を出力して終了。
   • 存在すれば、その区間の右端で covered を更新し、count をインクリメント。
5. 最終的に count を出力。

例

入力:

N = 10
M = 4
区間: [1,4], [2,6], [5,8], [7,10]

処理の流れ:

• 最初: covered = 0
• 開始位置 ≤ 1 の区間: [1,4] → 右端最大 = 4 → covered = 4, count = 1
• 開始位置 ≤ 5 の区間: [2,6], [5,8] → 右端最大 = 8 → covered = 8, count = 2
• 開始位置 ≤ 9 の区間: [7,10] → 右端 = 10 → covered = 10, count = 3

→ 答えは 3

計算量

• 時間計算量: \(O(M \log M)\) （ソートが支配的）
• 空間計算量: \(O(M)\)

実装のポイント

• 入力を高速に読み込む必要がある（Pythonの場合は sys.stdin.read などを使う）。
• 区間を開始位置でソートすることを忘れない。
• 「次のカバーすべき位置 (covered + 1)」を基準に選ぶ区間を判断することで、正しい貪欲法になる。

ソースコード

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    intervals = []
    index = 2
    for _ in range(M):
        L = int(data[index])
        R = int(data[index+1])
        intervals.append((L, R))
        index += 2
    
    # 区間を開始位置でソート
    intervals.sort()
    
    # 現在カバーされている最後の位置
    covered = 0
    i = 0
    count = 0
    
    while covered < N:
        # 次に選ぶ区間の右端の最大値
        max_reach = -1
        # 現在カバーされている位置から始まる区間の中で右端が最も大きいものを探す
        while i < M and intervals[i][0] <= covered + 1:
            max_reach = max(max_reach, intervals[i][1])
            i += 1
        
        # もしカバーできる区間がなければ不可能
        if max_reach == -1:
            print(-1)
            return
        
        # 選んだ区間でカバー範囲を更新
        covered = max_reach
        count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。