Maximum coverage area over a range.

Правка en1, от AKJ88, 2015-10-28 21:43:31

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AKJ88 2015-10-28 21:43:31 710 Initial revision (published)