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?
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.
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]
can u please explain?