Skip to main content
edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Source Link
Hauke Reddmann
  • 4.8k
  • 1
  • 18
  • 24

Maximum nonintersecting interval pick

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 :-)