## Greedy Heuristic

At every step, we choose the interval with a left endpoint <= the current uncovered position, and a right endpoint that stretches out the farthest.

fun minCover(var L, var R, var X, var n){
    var intervals; 
    
    sort(intervals.begin, intervals.end);
    
    var count = 0; 
    var i = 0; 
    var end = X.start - 1;
    
    while(i < n){
        var max_end = end;
        while(intervals[i].left <= X.start){
            max_end = max(max_end, intervals[i].right);
            i++;
        }
        if(max_end == end) return -1;
        
        count++;
        start = max_end;
        end = max_end;
        
        if(end >= X.end) break;

    return count;
}

## Greedy Choice Property Proof

First, suppose `s` represents an optimal solution with an interval spread covering [X.start, X.end]. Next, suppose `i_greedy` represents the greedy choice interval that stretches out the farthest from the current, *uncovered* position. Let `i_optimal` be the first interval of `s`.

**Claim:** If we use `i_greedy` as the first interval of `s` instead of `i_optimal`, we will still be covering the remainder of X.

**Proof:** If `s` covers `X.start, X.end`, and i_optimal represents the first interval in that range, since`i_greedy` extends well beyond the current uncovered position, it must at least cover `i_optimal`. That means it can easily replace whatever `i_optimal` was covering.

Naturally, if `i_greedy` covers *more* than `i_optimal`, it is more optimal, because it requires less intervals. Since it can always replace `i_optimal` at each step without increasing the number of intervals involved, **it is always part of an optimal solution.**