Interval covering problem

The given intervals [1,2], [3,5], [1,5], [2,4], [4,5], [3,6], [2,7], [7,9], [4,8], [1,3], we need the choice of intervals such that we can cover the entire interval [1,9].

Please tell me - how to solve it?

Sort intervals by their left border, and keep up the value of maximal prefix of covered points. To update it, find a new interval that will continue the prefix without no gaps, with maximal right border.

1 Like

can u please explain?

ok, so after sorting your intervals will look like this:

[1,5], [1,3], [1,2], [2,7], [2,4], [3,6], [3,5], [4,8], [4,5], [7,9].

So at first you will take [1,5]. now traverse over the intervals and look for the maximum right value. Here, it is [4,8]. You can’t take [7,9] in this step because then 6 wouldn’t be included.

At next step, take [7,9] and it will cover the whole interval.

So the answer is [1,5], [4,8], [7,9]

1 Like