Overview

This is a problem of finding the minimum number of intervals needed to completely cover the linear segment from section \(1\) to \(N\), using the union of \(M\) given intervals (ranges that guards can cover).

Analysis

This problem is a classic “cover interval \([1,N]\) with the minimum number of intervals” problem.

The key observation is as follows:

• Consider processing from left to right, where \(cur\) represents the leftmost section not yet guarded (initially \(cur=1\)).
• Among the guard candidates that contain \(cur\) (i.e., satisfy \(L_i \le cur\)), it is optimal to choose the one whose right endpoint \(R_i\) extends the farthest to the right.
  • Intuitively, if they can all guard \(cur\), choosing the one that covers the farthest distance at once will reduce the number of guards needed later.
  • If we choose a shorter interval here, we will end up needing additional guards later, which won’t yield the minimum.

A naive implementation of “searching all candidates each time” would take \(O(M)\) per step with potentially \(O(M)\) selection steps, resulting in worst-case \(O(M^2)\), which is too slow for \(M \le 2\times 10^5\). Therefore, we sort the intervals by their left endpoints and sweep from left to right in a single pass, updating “the maximum \(R\) among candidates that can guard \(cur\)”.

Also, if no candidate can cover \(cur\) (i.e., the maximum reachable point \(best < cur\)), then there is a “gap” in coverage at that point, making it impossible (output \(-1\)).

Concrete Example

For example, with \(N=10\) and intervals: - \([1,4], [2,8], [5,10]\)

At \(cur=1\), the only usable interval is \([1,4]\), so \(best=4\). We select one guard and set \(cur=5\). Next, at \(cur=5\), the usable intervals are \([2,8], [5,10]\), so \(best=10\). We select one more guard and \(cur=11\), completing the coverage. The answer is 2.

Algorithm

1. Sort all intervals \((L_i, R_i)\) in ascending order of \(L_i\).
2. Initialize variables:
   • \(cur\): the leftmost section not yet covered (initial value \(1\))
   • \(idx\): a pointer indicating how far we’ve scanned through the sorted intervals (initial value \(0\))
   • \(best\): the maximum right endpoint among intervals with \(L_i \le cur\) seen so far (initial value \(0\))
   • \(ans\): the number of guards selected (initial value \(0\))
3. While \(cur \le N\), repeat the following:
   • Process all intervals satisfying \(L_{idx} \le cur\), updating \(best = \max(best, R_{idx})\) while advancing \(idx\).
   • If \(best < cur\), then no interval can cover \(cur\), so output \(-1\) and terminate.
   • Otherwise, consider the interval with right endpoint \(best\) as selected: set \(ans \leftarrow ans + 1\) and update the next uncovered position to \(cur \leftarrow best + 1\).
4. Once the loop finishes, \([1,N]\) has been fully covered, so output \(ans\).

This greedy strategy of “among intervals that can cover the current point \(cur\), choose the one extending farthest to the right” is known to be correct for the minimum interval covering problem (provable by an exchange argument).

Complexity

• Time complexity: \(O(M \log M)\) for sorting and \(O(M)\) for the sweep, giving \(O(M \log M)\) overall.
• Space complexity: \(O(M)\) for the interval array.

Implementation Notes

• Although \(N\) can be up to \(10^9\), there is no need to maintain an array for all positions; we only process the interval information.

• Since the input can be large, we read it all at once using sys.stdin.buffer.read() and process it as a sequence of integers.

• best represents “the maximum right endpoint among all intervals seen so far with \(L_i \le cur\)”, and since it increases monotonically even after selecting intervals, it can be reused as-is.

• The impossibility check is done with best < cur (cannot advance = there is a gap).

  Source Code

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

---

This editorial was generated by gpt-5.2-high.