# Minimum number of Intervals to cover the Target Interval O(n) solution

• Any ideas please share and appreciate that.

Interview question, hope to help.
Choose from a list of intervals, to make full coverage of target interval with minimum selection. If cannot cover, return -1.
for example: [[3,6],[4,5],[7,10],[6,9],[7,12],[12,17],[10,13],[18,22],[16,18]]; target is [7, 22]; should return 3;

here is my solution, with O(n) time and O(n) space. The idea is similar to LeetCode 45. Jump Game II. The tricky part is how to find the starting point to just cover the target.start. Basically, it is a Greedy question. I used the "sweep line" like method to build an auxiliary array to mimic the Jump Game.

``````public class MinimumCoverInterval {
public int minimumCoverInterval(Interval[] intervals, Interval target) {
if (intervals == null || intervals.length == 0) return 0;
int min = Integer.MAX_VALUE;
int max = 0;
for (Interval i : intervals) {
min = Math.min(min, i.start);
max = Math.max(max, i.end);
}
int[] count = new int[max - min + 1];
for (Interval i : intervals) {
count[i.start - min] = Math.max(count[i.start - min], i.end - i.start);
}

int reach = 0;
int maxReach = 0;
int target_start = target.start - min;
int target_end = target.end - min;
int i = 0;
for (; i <= target_start; i++) {
if (i + count[i] < target_start) continue;
reach = Math.max(reach, i + count[i]);
}
int res = 1;
for (; i < count.length; i++) {
if (reach >= target_end) break;
maxReach = Math.max(maxReach, i + count[i]);
if (reach <= i) {
reach = maxReach;
res++;
}
}
return reach >= target_end ? res : -1;
}
}
``````

• ``````/**
Based on your example, it seems the input interval array is not sorted.
Sort the array of interval objects first. Then do a O(n) tarversal to find the minimum intervals needed for coverage.
Time complexity:O(nlogn) where n is the size of the input array of intervals.
**/
public class IntervalComparator<Interval> implements Comparator{
public int compare(Interval a, Interval b){
if(a.start == b.start){
return a.end - b.end;
}
return a.start - b.start;
}

}

public int minCover(Interval[] arr,Interval target){
Arrays.sort(arr,new IntervalComparator());
int i = 0;
while(i < arr.length){
if(arr[i].end < target.start){
i++;
}
}

int count = 0;
while(target.start <= target.end){
Interval best = null;
while(i < arr.length && arr[i].start <= target.start){
if(best == null || arr[i].end > best.end){
best = arr[i];
i++;
}
}
if(best == null){
return -1;
}
count++;
target.start = best.end + 1;
}
return count;
}``````

• @divyam01986 your solution has some problem regarding following test case:

(0,3) (4,7), target is (0,7), I think it should output 0, but your algorithm output 2.

• Same as jump game II

``````Arrays.sort(list, new Comparator<Interval>(){
public int compare(Interval a, Interval b) {
if (a.start != b.start) {
return a.start - b.start;
}
return a.end - b.end;
}
});

int num = 0, i = 0, start = interval.start, end = -1;
while (i < list.length) {
if (list[i].end <= start) {
i++;
} else {
if (list[i].start > start) break;
while (i < list.length && list[i].start < start) {
end = Math.max(end, list[i].end);
i++;
}
if (start != end) {
num++;
start = end;
}
}
}

if (end < interval.end)
return 0;
return num;
``````

• @sheva It's a nice solution but it ain't O(n) time/space. The size of your `count` array is dependent on the ranges of the input intervals. E.g. if you're given a single interval [1,1M], you'll end up with 1M time and space.
The only way I see to avoid it is to keep that values in a sorted map, but that will cost you O(nlogn) for the insertions.

• @FunCode ouput should be 2, algo is correct.
You see 0-3 then 4-7 is leading to 0-7.
If you look closely, so is in the question itself:
[7,12],[12,17],[18,22], target is [7,22], output is 3

• @xmztzt fif First of all, the condition start != end is redundant. Plus, no interval is found, you can just return num .

• Here is my codes in C.

int minimum_intervals(int* begin, int* end, int len, int* range)
{
int min, max, i;
int *scale, length, index, gap;
int start, maxindex, maxcover, count;

``````//search for minimum and maximum of begins
min = 1000000;
max = 0;

for (i = 0; i < len; i++)
{
min = (min > begin[i]) ? begin[i] : min;
max = (max < begin[i]) ? begin[i] : max;
}

//Create an array to hold ranges, sorted
length = max - min + 1;
scale = (int*) malloc(length * sizeof(int));

for (i = 0; i < length; i++)
{
scale[i] = 0;
}

for (i = 0; i < len; i++)
{
index = begin[i] - min;
gap = end[i] - begin[i];
scale[index] = (scale[index] < gap) ? gap : scale[index];
}

// using greedy algorithm to search for ranges.
i = 0;
start = range[0] - min;
maxindex = 0;
maxcover = 0;
count    = 0;

while (i < length)
{
if (start >= range[1] - min)
{
printf("found a set of intervals\n");
free(scale);
return count;
}

if (maxcover < scale[i]+i)
{
maxcover = scale[i] + i;
maxindex = i;
}

if (i == start)
{
printf("[%d, %d]", maxindex+min, maxcover+min);
start = maxcover+1;
count++;
}
else
{
i++;
}
}
printf("didn't find a set of intervals\n");
free(scale);
return -1;
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.