概要

区画 \(1\) から \(N\) までの直線区間を、与えられた \(M\) 個の区間（警備員が担当できる範囲）の和集合で完全に覆うために必要な最小個数を求める問題です。

考察

この問題は「区間 \([1,N]\) を最小本数の区間で被覆する」典型問題です。

重要な観察は次の通りです。

• いま左から順に「まだ警備できていない最左の区画」を \(cur\) とします（最初は \(cur=1\)）。
• \(cur\) を含む（つまり \(L_i \le cur\) を満たす）警備員候補の中から、右端 \(R_i\) が最も右まで伸びるものを選ぶのが最適です。
  • 直感的には、同じ \(cur\) を守れるなら、より遠くまで一気にカバーできる方が後で必要な人数が減ります。
  • ここで短い区間を選んでしまうと、結局後で追加の警備員が必要になり、最小になりません。

素朴に「毎回候補を全部探す」実装をすると、各ステップで \(O(M)\) 探して最大 \(O(M)\) 回選ぶ可能性があり、最悪 \(O(M^2)\) になって \(M \le 2\times 10^5\) では間に合いません。
そこで、区間を左端でソートしておき、左から一度なめるだけで「\(cur\) を守れる候補の中で最大の \(R\)」を更新できるようにします。

また、どの候補を見ても \(cur\) を覆えない（最大到達点 \(best < cur\)）なら、その時点で区間に“穴”があるので不可能（\(-1\)）です。

具体例

例えば \(N=10\)、区間が - \([1,4], [2,8], [5,10]\) のとき、\(cur=1\) で使えるのは \([1,4]\) だけなので \(best=4\)、1人選んで \(cur=5\)。
次に \(cur=5\) で使えるのは \([2,8], [5,10]\) なので \(best=10\)、もう1人で \(cur=11\) となり完了、答えは 2 です。

アルゴリズム

1. すべての区間 \((L_i, R_i)\) を \(L_i\) 昇順でソートする。
2. 変数を用意する：
   • \(cur\): まだ覆われていない最左の区画（初期値 \(1\)）
   • \(idx\): ソート済み区間をどこまで見たかのポインタ（初期値 \(0\)）
   • \(best\): 現時点で選べる区間（\(L_i \le cur\)）の中で最大の右端（初期値 \(0\)）
   • \(ans\): 選んだ警備員数（初期値 \(0\)）
3. \(cur \le N\) の間、以下を繰り返す：
   • \(L_{idx} \le cur\) を満たす区間をすべて取り込み、\(best = \max(best, R_{idx})\) を更新しながら \(idx\) を進める。
   • もし \(best < cur\) なら、\(cur\) を覆える区間が存在しないので \(-1\) を出力して終了。
   • そうでなければ、右端が \(best\) の区間を選んだとみなし、\(ans \leftarrow ans + 1\)、次の未被覆位置を \(cur \leftarrow best + 1\) に更新する。
4. ループが終われば \([1,N]\) を覆い切ったので \(ans\) を出力する。

この貪欲法は「今覆うべき点 \(cur\) を覆える区間の中で、最も右へ伸びるものを選ぶ」戦略で、区間被覆の最小本数問題で正しいことが知られています（交換法で示せます）。

計算量

• 時間計算量: ソートに \(O(M \log M)\)、走査は \(O(M)\) なので全体で \(O(M \log M)\)
• 空間計算量: 区間配列に \(O(M)\)

実装のポイント

• \(N\) は最大 \(10^9\) ですが、座標全体を配列で持つ必要はなく、区間の情報だけで処理できます。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み、整数列として処理しています。

• best は「これまでに見た、\(L_i \le cur\) を満たす区間の最大の右端」を表し、区間を選んだ後も（単調に）増えるのでそのまま使い回せます。

• 不可能判定は best < cur（次に進めない＝穴がある）で行います。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    intervals = [(data[i], data[i + 1]) for i in range(2, 2 + 2 * M, 2)]
    intervals.sort()

    cur = 1
    idx = 0
    best = 0
    ans = 0

    while cur <= N:
        while idx < M and intervals[idx][0] <= cur:
            if intervals[idx][1] > best:
                best = intervals[idx][1]
            idx += 1
        if best < cur:
            print(-1)
            return
        ans += 1
        cur = best + 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。