# Minimum cover of intervals

#### Heurisic
The goal here is to find the smallest subset $Y \subseteq X$ such that the Union(Y) = Union(X). This problem is about identifying and removing redundant intervals.

An interval $I_i$ in the set $X$ is defined as redundant if it is fully contained within the union of all other intervals in $X$. That is, $I_i \subseteq \bigcup_{j \neq i}\ I_j$. An interval $I_i$ is non-redundant if it fails this requirement.

**Heuristic**: The smallest cover $Y$ is the set of all non-redundant intervals. The greedy choice is to select/keep every interval $I \in X$ that is non-redundant.

#### Proof
We must prove that this greedy choice (keeping all non-redundant intervals) leads to a globally optimal solution.

Let $Y^{'}$ be any smallest cover for $X$. We must show that every non-redundant interval $I_k \in X$ is also in $Y^{'}$.
Let $I_k$ be any non-redundant interval in $X$. By the definition of non-redundant, $I_k$ is not fully contained in the union of all other intervals. $I_k \not\subseteq \bigcup_{k \neq j} I_j$

Therefore, there must exist at least one point $p$ such that: $p \in I_k$ and $p \notin \bigcup_{k \neq j} I_j$. The full union of all intervals in $X$ (Union($X$)), must contain the point $p$ because $I_k$ is part of $X$.

Now, the smallest cover $\ Y^{'}$, by the problem's definition, $Y^{'} \subseteq X$ and its union must be identical to the total union. Union($Y{'}$) = Union($X$)
Therefore, the union of the cover $Y^{'}$ must also contain the point $p$. $p \in \bigcup Y^{'}$

We know that the only interval in the entire original set $X$ that contains $p$ is $I_k$. Since $Y^{'}$ is just a subset of $X$, the only way Union($Y^{'}$) can contain $p$ is if $I_k$ is an element of $Y^{'}$.
Therefore, any non-redundant interval $I_k$ must be included in any valid cover, and thus must be part of the smallest cover $Y^{'}$.