概要

区間 \([1, N]\) をカバーするように、与えられた複数の区間から最小個数の区間を選択する問題です。

考察

この問題は、区間スケジューリング問題の一種ですが、通常のものとは異なり、区間全体をカバーするための最小個数を求める問題です。重要な観察は以下の通りです：

1. 貪欲法の適用: 左端から順にカバーしていく貪欲法が有効です。現在カバーされている範囲を \([1, current]\) とし、\(current+1\) を含む区間の中で最も右端が遠いものを選ぶのが最適です。

2. 区間の前処理: 区間を左端の昇順、同じ左端の場合は右端の降順でソートします。これにより、効率的に次に選ぶべき区間を探索できます。

3. 不可能な場合の判定: 現在のカバー範囲から次の区間を選べない場合（\(candidate \leq current\) のとき）は、カバー不可能なので \(-1\) を返します。

アルゴリズム

1. 入力読み込み: 区間の数 \(N\) と警備員の数 \(M\)、各警備員の区間 \([L_i, R_i]\) を読み込みます。
2. 区間のソート: 区間を左端 \(L_i\) の昇順、同じ左端の場合は右端 \(R_i\) の降順でソートします。
3. 貪欲な選択:
   • \(current = 0\) (現在カバーされている右端) から開始します。
   • \(current < N\) の間、以下を繰り返します：
     • \(current+1\) 以下の左端を持つ区間の中で、最も右端が大きい区間を選択します（\(candidate\)）。
     • もし \(candidate \leq current\) ならカバー不可能なので \(-1\) を出力して終了します。
     • \(current\) を \(candidate\) に更新し、カウントを増やします。
4. 結果出力: 必要な警備員の最小人数を出力します。

計算量

• 時間計算量: \(O(M \log M)\) （ソートが支配的）
• 空間計算量: \(O(M)\) （区間を保存するため）

実装のポイント

• ソートの際、同じ左端の区間は右端が大きい順に並べることで、効率的に最適な区間を選択できます。

• 現在カバーする範囲の右端を \(current\) とし、\(current+1\) をカバーする区間を探すことで、連続性を保ちます。

• インデックスの管理を適切に行い、同じ区間を何度もチェックしないようにします。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    intervals = []
    index = 2
    for i in range(m):
        l = int(data[index])
        r = int(data[index+1])
        index += 2
        intervals.append((l, r))
        
    intervals.sort(key=lambda x: (x[0], -x[1]))
    
    if not intervals:
        print(-1)
        return
        
    current = 0
    next_reach = 0
    count = 0
    i = 0
    while current < n:
        candidate = current
        while i < m and intervals[i][0] <= current + 1:
            if intervals[i][1] > candidate:
                candidate = intervals[i][1]
            i += 1
            
        if candidate <= current:
            print(-1)
            return
            
        current = candidate
        count += 1
        
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。