Greedy filling unit intervals

Question

I have unit intervals given such as $I = \{\{s_1, s_1 + 1\}, ..., \{s_k, s_k+1\}\}$ ($\forall s_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one interval.

I am asked to suggest a greedy algorithm to minimize the number of intervals required to capture all reals from $X$.

My attempt: Sort intervals by starting (or equivalently finishing) time. Sort numbers in $X$. Then, for the first entry in (sorted) $X$, place it in the latest intervals that can catch it. Then check if the next element of $X$ fits in this interval, if not, place in the latest interval that can catch it.

Questions that arised: how can I prove the correctness of my algorithm?

Answer 1

The greedy algorithm

1. Let $result$ be an empty set and let $last\_interval$ be none.
2. For each $num$ in sorted $X$:
   • If $num$ is not covered by the last interval:
     1. let $last\_interval$ be the interval with the latest starting time among all intervals that cover $num$.
     2. Add $last\_interval$ to $result$.
3. Return $result$.

How can we prove the greedy algorithm is correct?

Let us prove the greedy algorithm "stays ahead", since it is clear visually that each interval selected by the greedy algorithm always pushes the latest covered number (time) to the future as far as possible while covering all numbers earlier than that latest covered number.

We can capture that intuition by the formal claim below.

Claim. Suppose the greedy algorithm returns intervals $g_1, g_2, \cdots, g_{n_g}$. Suppose another algorithm returns intervals $a_1, a_2, \cdots, a_{n_a}$, which are, WLOG, also in increasing order of starting time. Then the finishing time of $g_i$ is not earlier than that of $a_i$ for all $i\le n_g$ and $n_g\le n_a$.
Proof. It is easy to prove by induction on $i=1,2,\cdots$. Readers can fill the details.