## Minimum cover of intervals

## Problem

We are given a set X of n intervals on the real line, represented by two arrays L[1..n] and R[1..n] for their left and right endpoints.
A subset Y ⊆ X covers X if the union of intervals in Y equals the union of intervals in X.
Our goal is to compute the smallest subset Y that covers X.

## Greedy Heuristic

We first sort all intervals by their starting point L[i] (and by decreasing R[i] if two intervals start at the same point).
Starting from the leftmost uncovered point p, we repeatedly select the interval that begins at or before p and extends farthest to the right.
We then move p to that right endpoint and continue until the entire union of intervals is covered.

## Proof of Greedy Choice Property

Let p be the current leftmost uncovered point.
Any valid cover must include some interval that starts at or before p, otherwise p cannot be covered.
Among these candidates, our greedy choice picks the one that extends the farthest to the right.
This choice is safe because it covers at least as much as any other interval starting before p; therefore, replacing any shorter interval with our greedy choice cannot increase the total number of intervals in an optimal solution.

By the exchange argument, there exists an optimal cover that includes our greedy choice.
Repeating this process for every uncovered portion guarantees an overall optimal solution.

## Time Complexity

Sorting requires O(n log n) time, and scanning through the intervals once requires O(n).
Hence, the total time complexity is O(n log n).