Overview

This problem is an “interval covering problem” where we need to select the minimum number of intervals from the given \(M\) intervals \([L_i, R_i]\) to completely cover the range \([1, N]\).

Analysis

Greedy Approach

To find the minimum number of people (intervals), a greedy approach is effective: “Among the intervals that start from right after the currently covered range, choose the one that reaches the farthest to the right.”

For example, suppose sections \(1\) through \(X\) are currently covered. The next guard to select must satisfy the following conditions: 1. No gaps: The left endpoint \(L_i\) of the guard’s assigned range must be at most \(X+1\). 2. Maximize efficiency: Among the guards satisfying condition 1, choose the one with the largest (farthest-reaching) right endpoint \(R_i\).

By repeating this selection, we can always reach the target \(N\) with the minimum number of people.

Why This Method Works

Since \(N\) can be as large as \(10^9\), we cannot examine each section one by one. However, since the number of guards \(M\) is at most around \(2 \times 10^5\), we can solve it within the time limit by efficiently processing the guards’ information.

By sorting by the left endpoint \(L_i\), we can sequentially examine the “next usable candidates,” keeping the computational complexity low.

Algorithm

1. Sort: Sort the list of guards in ascending order of their left endpoint \(L_i\).
2. Initialize: Set the current covered right endpoint to current_rightmost = 0.
3. Loop: While current_rightmost is less than \(N\), repeat the following:
   • Check all guards whose \(L_i\) is at most current_rightmost + 1.
   • Find the one with the maximum \(R_i\) among them, and call it next_rightmost.
   • If no guard is found that can extend current_rightmost, it is impossible to cover all sections, so output -1 and terminate.
   • Hire the guard that reaches the farthest, and update current_rightmost with their \(R_i\).
4. Termination: Once current_rightmost reaches \(N\), output the number of hired people.

Complexity

• Time Complexity: \(O(M \log M)\)
  • Sorting the guards takes \(O(M \log M)\).
  • The subsequent scan examines each guard only once, so it is \(O(M)\).
  • Overall, sorting is the dominant factor.
• Space Complexity: \(O(M)\)
  • Required to store the \(M\) interval information in a list.

Implementation Notes

• Importance of sorting: By performing intervals.sort(), we can efficiently search in order of increasing left endpoints.

• Termination condition check: The condition while idx < M and intervals[idx][0] <= current_rightmost + 1 ensures that we check all intervals starting from “right next to” the currently covered range, without missing any or checking duplicates.

• Handling large \(N\): The value of \(N\) itself does not directly affect the number of loop iterations; it is only used for the termination check. Therefore, even a value as large as \(10^9\) works without issues.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.