0
$\begingroup$

This surely has been solved in the context of scheduling already! (Shall I ask on some computer SE instead?)

Assume we have a set of closed "intervals" on $\mathbb Z$ ($\mathbb R$ isn't different, I guess) and like to pick the maximum cardinality of nonintersecting intervals from it. I bet the obvious greedy algorithm (first throw out all intervals that completely enclose another, then pick leftmost, repeat) already gives the solution.

A reference would suffice. (If the proof is trivial, please leave it to me :-)

Improve this question
$\endgroup$
2
  • $\begingroup$ Is this it? en.wikipedia.org/wiki/Interval_scheduling $\endgroup$
    – Ben Barber
    Commented Jun 19, 2020 at 11:02
  • 1
    $\begingroup$ Bingo and THX! I admit I could have found that myself if I wanted to and weren't too lazy (those summer temperatures :-). Question can be closed, I can find the original literature with a formal proof of the greedy algorithm myself. $\endgroup$
    – Hauke Reddmann
    Commented Jun 19, 2020 at 11:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .