Greedy Algorithm — Intervals

Revision en1, by coder_1560, 2017-03-12 08:17:39

I was trying to solve a problem. Given a set of black and white intervals, select a smallest number of white intervals that collectively overlap every black interval.

I know it's greedy but can't exactly figure out why. Also, proving greedy is a little difficult. Can someone using greedy please prove it formally.

Thanks in advance!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English coder_1560 2017-03-12 08:17:39 368 Initial revision (published)