概要

この問題は、与えられた \(M\) 個の区間 \([L_i, R_i]\) を使って、範囲 \([1, N]\) を完全に覆うために必要な最小の区間数を選択する「区間被覆問題」です。

考察

貪欲法によるアプローチ

最小の人数（区間数）を求めるため、「今カバーできている範囲のすぐ次から始まる区間のうち、最も右側（遠く）まで届くものを選ぶ」という貪欲法が有効です。

例えば、現在区画 \(1\) から \(X\) までがカバーされているとします。次に選ぶべき警備員は、以下の条件を満たす必要があります。 1. 隙間を作らない: その警備員の担当範囲の左端 \(L_i\) が \(X+1\) 以下であること。 2. 効率を最大化する: 条件1を満たす警備員の中で、右端 \(R_i\) が最も大きい（遠くまで届く）こと。

この選択を繰り返すことで、常に最小の人数で目標の \(N\) まで到達することができます。

なぜこの方法で解けるのか

\(N\) が最大 \(10^9\) と非常に大きいため、区画を一つずつ調べることはできません。しかし、警備員の数 \(M\) は \(2 \times 10^5\) 程度であるため、警備員の情報を効率よく処理することで制限時間内に解くことが可能です。

左端 \(L_i\) でソートしておけば、「次に使える候補」を順番に見ていくことができ、計算量を抑えられます。

アルゴリズム

1. ソート: 警備員のリストを左端 \(L_i\) の昇順にソートします。
2. 初期化: 現在カバーできている右端を current_rightmost = 0 とします。
3. ループ: current_rightmost が \(N\) 未満である間、以下を繰り返します。
   • 現在の current_rightmost + 1 以下の \(L_i\) を持つ警備員をすべてチェックします。
   • その中で最大の \(R_i\) を持つものを探し、それを next_rightmost とします。
   • もし current_rightmost を更新できる警備員が見つからなければ、すべての区画をカバーすることは不可能なので -1 を出力して終了します。
   • 最も遠くまで届く警備員を 1 人採用し、current_rightmost をその \(R_i\) で更新します。
4. 終了: current_rightmost が \(N\) に達したら、採用した人数を出力します。

計算量

• 時間計算量: \(O(M \log M)\)
  • 警備員のソートに \(O(M \log M)\) かかります。
  • その後の走査は、各警備員を一度ずつしか見ないため \(O(M)\) です。
  • 全体としてソートが支配的になります。
• 空間計算量: \(O(M)\)
  • \(M\) 個の区間情報をリストに保持するために必要です。

実装のポイント

• ソートの重要性: intervals.sort() を行うことで、左端が小さい順に効率よく探索できるようになります。

• 終了条件の判定: while idx < M and intervals[idx][0] <= current_rightmost + 1 という条件により、現在カバーしている範囲の「すぐ隣」から始まる区間を漏れなく、かつ重複なくチェックしています。

• 大きな \(N\) への対応: \(N\) の値自体はループの回数に直接影響せず、あくまで終了判定に使われるだけなので、\(10^9\) という大きな値でも問題なく動作します。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込みます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 区画の数, M: 警備員候補の数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各警備員の担当範囲 (L_i, R_i) をリストに格納します
    intervals = []
    for i in range(M):
        l = int(input_data[2 + 2 * i])
        r = int(input_data[3 + 2 * i])
        intervals.append((l, r))
        
    # 区間の左端 L_i に基づいて昇順にソートします
    # これにより、現在カバーされている範囲の直後から始まる区間を効率的に探せます
    intervals.sort()
    
    current_rightmost = 0  # 現在確実にカバーされている範囲の右端
    next_rightmost = 0     # 次のステップで到達可能な最大の右端
    guards_count = 0       # 配置した警備員の数
    idx = 0                # 現在見ている intervals のインデックス
    
    # 1からNまでのすべての区画をカバーするまで繰り返します
    while current_rightmost < N:
        # 現在カバーされている範囲 (current_rightmost) のすぐ隣、
        # つまり current_rightmost + 1 をカバーできる区間をすべて調べ、
        # その中で最も遠く (右) までカバーできるものを選びます。
        found_extension = False
        while idx < M and intervals[idx][0] <= current_rightmost + 1:
            if intervals[idx][1] > next_rightmost:
                next_rightmost = intervals[idx][1]
                found_extension = True
            idx += 1
            
        # もし current_rightmost を更新（延長）することができなければ、
        # 隙間ができてしまい、Nまで到達することは不可能です。
        if next_rightmost <= current_rightmost:
            print("-1")
            return
            
        # 最も遠くまで届く区間を採用し、現在の右端を更新します
        current_rightmost = next_rightmost
        guards_count += 1
        
    # 最小の警備員数を出力します
    print(guards_count)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。