Overview

A problem to find the minimum number of guards to cover sections on a line. Each guard can cover a continuous range, and we use a greedy method to find the minimum number of guards to select in order to cover the entire line.

Analysis

This problem is a variant of the classic “interval scheduling problem,” where the greedy approach of “selecting the guard that covers the widest range possible” is effective.

Key Observations

• At each step, among the guards that can cover the “next uncovered point” (i.e., covered + 1) from the currently covered sections, it is optimal to select the one that covers the farthest.
• This allows covering a wide range with fewer guards.

With a Naive Approach…

• Trying all combinations with brute force takes exponential time (TLE).
• Also, simply selecting non-overlapping intervals may fail to cover the entire range (WA).

Solution

• Sort the intervals by their starting positions and iterate through them in order, at each step selecting the interval that reaches the farthest among those that can cover the “next point to be covered.”
• This allows covering the entire range with the minimum number of intervals.

Algorithm

1. Sort all intervals in ascending order by their starting position \(L_i\).
2. covered: the right endpoint of the currently covered sections (initially 0).
3. count: the number of selected guards.
4. While covered < N, repeat the following:
   • Among the intervals whose starting position is at most covered + 1, select the one with the maximum right endpoint.
   • If no such interval exists, output -1 and terminate.
   • If one exists, update covered with the right endpoint of that interval and increment count.
5. Finally, output count.

Example

Input:

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

Processing flow: - Initially: covered = 0 - Intervals with starting position ≤ 1: [1,4] → maximum right endpoint = 4 → covered = 4, count = 1 - Intervals with starting position ≤ 5: [2,6], [5,8] → maximum right endpoint = 8 → covered = 8, count = 2 - Intervals with starting position ≤ 9: [7,10] → right endpoint = 10 → covered = 10, count = 3

→ The answer is 3

Complexity

• Time complexity: \(O(M \log M)\) (dominated by sorting)
• Space complexity: \(O(M)\)

Implementation Notes

• Input needs to be read efficiently (in Python, use sys.stdin.read, etc.).

• Don’t forget to sort the intervals by their starting positions.

• By using “the next position to be covered (covered + 1)” as the criterion for selecting intervals, the greedy method works correctly.

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.