Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some point, that is $\forall I \in \mathcal{I}: \exists p \in P, p \in I$.
Interval Scheduling Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a maximum number of intervals such that no two of them overlap.
Interestingly, the two problems above have exactly the same greedy algorithm, illustrated by the following figure (from [1]; for the interval scheduling problem; see the "Greedy Algorithm" part below).
Since they share the same algorithm, I expect that they are the same (or, at least closely related) problem, say, in the view of reduction. However, I failed to reduce them to each other.
Question: Are these two problems the same? Or what is the relation between them? Can we reduce them to each other?
Note that the first problem asks for a minimum solution while the second one for a maximum solution.
Greedy Algorithm: The greedy algorithm for the "Interval Scheduling" problem is as follows:
- sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
- while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:
- add $I$ into the result-set; (darker lines in the figure)
- delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).
For the "Point-Cover-Interval" problem, we simply collect the finishing time point of each interval $I$ chosen in each iteration in the algorithm above.
[1]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)