coder_1560's blog

Greedy Algorithm — Intervals
By coder_1560, history, 8 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you clarify 'collectively overlap'? Do you have to simply touch each black interval at least once or does each black interval have to be entirely covered by white?

→ Reply