AKJ88's blog

By AKJ88, history, 9 years ago, In English

I am faced with a problem in real world and couldn't get the optimal solution for that.

Imagine that we have several ranges over [0..n] and we want to choose several of them in a way that cover this range in the best way possible, without intersecting with one another. A simplified version of this problem can be found in UVA-10020-Minimal coverage.

For example if n==10 we can have the following ranges to choose from:

[0..2]

[0..3]

[1..5]

[6..8]

[7..10]

And the desired answer would be [1..5] & [7..10].

Obviously greedy is not the right approach in this problem.

I would really appreciate it if someone could help me in solving this problem.

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it