# minimum cover of intervals ## problem: Let X be a set of n intervals on the real line. We say that a subset of intervals Y ⊆ X covers X if the union of all intervals in Y is equal to the union of all intervals in . The size of a cover is just the number of intervals. Describe an efficient algorithm to compute the smallest cover of X. State the greedy heuristic and prove its greedy choice property. Assume that your input consists of two arrays L[1..n] and R[1..n], representing the left and right endpoints of the intervals in X. ## algorithm: The greedy heuristic is to, at each step, always select the interval that starts at or before the current uncovered point and extends the farthest to the right. ## correctness: #### Theorem: The greedy algorithm correctly identifies the smallest cover of X. #### Proof: Greedy Choice Property Proof: If the algorithm is at the leftmost uncovered point p, then there must exist an optimal solution that includes the interval starting at or before p that extends the farthest to the right. Let I~g~ be the interval chosen that starts at or before p and extends farthest right. Let I~o~ be the first interval in some optimal solution that covers p. - By definition, L[I~o~] is less than or equal to p is less than or equal to R[I~o~]. - The greedy choice ensures that R[I~g~] is greater than or equal to R[I~o~] because I~g~ extends the farthest to the right among all intervals starting before or at p. Now, if you replace I~o~ in the optimal solution with I~g~, coverage is not decreased and the number of intervals is not increased, meaning that the resulting set is still optimal. Therefore, there exists an optimal solution containing the greedy choice I~g~, proving the greedy choice property. Inductive Optimality Proof: Let S be the segment of the union of intervals the are yet to be covered. 1. Base Case: The first interval chosen by the algorithm is optimal by the above greedy choice property. 2. Inductive Step: After selecting I~g~, we can restrict the problem to the uncovered portion. The residual problem has the exact same structure. By the induction hypothesis, the greedy solution on the remaining part of the problem is optimal. 3. Therefore, the entire greedy algorithm yields an optimal minimal cover.