# **Minimum Cover of Intervals**

You only need to state your greedy Heuristic and prove its greedy choice property.
# **Greedy Heuristic**
* sort intervals by left endpoint
* go left --> right. Let p be the leftmost point not covered in the union
* in all intervals with Li <= p, pick the interval with the largest right endpoint Ri
* if there are still intervals but none of them start less than or equal to p, move p to the left endpoints of the next interval, repeat
# **Greedy Choice Property**
Goal: the greedy algorithm finds and returns the smallest set of intervals that cover the same union as all intervals

* Suppose an optimal solution picks some first interval J that starts at or before p and ends at Rj.
* the greedy choice G also starts at or before p and Rg >= Rj
* if we replace J with G --> the number of intervals does not increase, the portion of the line covered after p is at least as large

Thus, there is always an optimal solution that makes the greedy choice at the first step. By applying this logic at each uncovered point, the algorithm should return an overall optimal cover.
# **Time Complexity**
* sorting --> O(nlogn)
* single pass selection --> O(n)

T(n) = O(nlogn)