# Problem:
Let X be a set of *n* intervals on the real line. Y is a subset of X and covers X. if the union of intervals in *Y* equals the union of intervals in *X*. the task is to find the smallest cover of *X*

# Sample Solution:

algorithm descripition

Greedy Heuristic
1. Sort all intervals in X by their left endpoint (increasing order)
2. Update variable current_end (point furthest to the right covered so far)
3. each step, all interval tht left endpoint < (or equal) current_end,
select the one with the largest right endpoint.
4. Add that into the cover, update current_end to that value
5. Repeat until the union of intervals covers the range of X

Greedy Choice Property
Every step is choosing the interval that extends the current coverage the farthest is safe / optimal
* Assume the optimal cover inlcudes a different interval that starts before or at the same
place but ends earlier.
* replacing that interval with the greedy one,can't worsen coverage, or increase intervals.
* Therefor, the greedy chocie never prevents reaching optimal solution. (even tho it's bad)
By Induction, the greedy algo always yields smallest possible cover. 

# correctness proof
Base Case
* For the first interval, the greedy chocie maximizes intial coverage
Inductive Step
* I will Assume the greedy algo covers up to point p. the next greedy interval max's the extension beyond P. any optimal solution must also include an interval starting before P, and ending no later than the greedy one. if that happens the coverage breaks and the algo is false.
* Hence the algo constructs an optimal minimal cover.
# time complexity
I am assuming we do not need this as the assignment stated "*I only need to state the greedy heuristic, and prove it's greedy chocie property"