Overview

This is a problem of selecting the minimum number of intervals from a given set of intervals to cover the range \([1, N]\).

Analysis

This problem is a variant of the interval scheduling problem, but unlike the standard version, it asks for the minimum number of intervals needed to cover the entire range. The key observations are as follows:

1. Applying a greedy approach: A greedy method that covers from left to right is effective. Let the currently covered range be \([1, current]\), and among the intervals that contain \(current+1\), it is optimal to select the one whose right endpoint extends the farthest.

2. Preprocessing the intervals: Sort the intervals in ascending order of their left endpoints, and in descending order of their right endpoints for intervals with the same left endpoint. This allows efficient searching for the next interval to select.

3. Determining impossible cases: If no next interval can be selected from the current coverage range (i.e., when \(candidate \leq current\)), covering is impossible, so return \(-1\).

Algorithm

1. Read input: Read the number of positions \(N\), the number of guards \(M\), and each guard’s interval \([L_i, R_i]\).
2. Sort intervals: Sort the intervals in ascending order of the left endpoint \(L_i\), and in descending order of the right endpoint \(R_i\) for intervals with the same left endpoint.
3. Greedy selection:
   • Start with \(current = 0\) (the right endpoint currently covered).
   • While \(current < N\), repeat the following:
     • Among the intervals whose left endpoint is at most \(current+1\), select the one with the largest right endpoint (\(candidate\)).
     • If \(candidate \leq current\), covering is impossible, so output \(-1\) and terminate.
     • Update \(current\) to \(candidate\) and increment the count.
4. Output result: Output the minimum number of guards required.

Complexity

• Time complexity: \(O(M \log M)\) (dominated by sorting)
• Space complexity: \(O(M)\) (for storing the intervals)

Implementation Notes

• When sorting, arranging intervals with the same left endpoint in descending order of right endpoint allows efficient selection of the optimal interval.

• By letting \(current\) be the right endpoint of the currently covered range and searching for intervals that cover \(current+1\), continuity is maintained.

• Manage indices properly to avoid checking the same interval multiple times.

  Source Code

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

This editorial was generated by deepseekv3.