# Find least number of intervals from A that can fully cover B

• Given a list of intervals A and one interval B, find the least
number of intervals from A that can fully cover B.

If cannot find any result, just return 0;

For example:
Given A=[[0,3],[3,4],[4,6],[2,7]] B=[0,6] return 2 since we can use [0,3] [2,7] to cover the B
Given A=[[0,3],[4,7]] B=[0,6] return 0 since we cannot find any interval combination from A to cover the B

• Could we sort the array by start time? Each time we select greedily an interval which starts at or before current start point point and is the farthest interval.
for example .
[0,3],[2,7][3,4][4,6]

1. we select 0,3 because this is the only option
2. we make a choice between [2,7], [3,4] and takes [2,7] because 7-3 > 4-3
So we choose 2 intervals

• ``````class Interval implements Comparable<Interval> {
int start;
int end;
Interval(int s,  int e)  {
start  =  s;
end  =  e;
}
public String toString()  {
return String.format("%d %d" ,start, end);
}
@Override
public int compareTo(Interval o) {
i f(star t!= o.start)
return start  -  o.start;
else
return end  -  o.end;
}
}

int minNumberOfIntervals(Interval[] list, Interval interval) {
Arrays.sort(list);
System.out.println(Arrays.toString(list));
int i = 0;
int start = interval.start;
int max = -1;
int num = 0;
while (i < list.length && max < interval.end) {
if (list[i].end <= start)
i++;
else {
if (list[i].start > start)
break;
while (i < list.length && max < interval.end && list[i].start <= start) {
if (list[i].end > max) {
max = list[i].end;
}
i++;
}
if (start != max) {
start = max;
num++;
}

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

• @elmirap Can you prove the greedy property here ? For me its not trivial to prove that the greedy solution works. I would try a dynamic programming approach. So I'm curious about your approach.
Thank you.

• ``````import sys

def mysort(lis):
return lis[0]

def interval(a, b):
a.sort(key=mysort)
s_index = sys.maxint
e_index = sys.maxint
f = False
for i in a:
if i[0] <= b[0]:
s_index = a.index(i)
f = True
break

if f:
for i in a[s_index:]:
if i[1] >= b[1]:
e_index = a.index(i)
break

else:
return -1

if e_index < sys.maxint:
if a[e_index][0] <= a[s_index][1]:
intervals = [a[s_index], a[e_index]]
return intervals

intervals = []
prev = a[s_index]
for i in a[s_index+1:e_index+1]:
if i[0] <= prev[1]:
intervals.append(i)
if i[1] >= a[e_index][0]:
return intervals
prev = i

return -1
else:
return -1

print interval(a,b)``````

• @galster Say we have a better (fewer intervals) solution which disagrees with the one from the greedy approach, and let their first disagreement interval to be i and i' respectively. Due to the greedy nature, we conclude that i'.end >= i.end, which allows us to cut and paste the rest of the intervals from i to substitute the rest intervals from the greedy solution from i', thus the greedy will generate no worse solution than the actual optimal.

• Here's a python pseudocode to solve it using dp approach

``````def solve(A,B):
sorted(A,key=lambda x:x[0])
n=len(A)
for i in range(n):
if(A[i][0]<=B[0]):
startidx=i
break
for i in range(startidx,n):
if(A[i][1]>=B[1]):
endidx=i
break
#dp[i] denotes the minimum number of intervals required to cover (B[0],B[i])
dp=[sys.maxint for i in range(B[0],B[1]+1)]
for i in range(A[startidx][0],A[startidx][1]+1):
dp[i]=1

for i in range(startidx+1,endidx):
start=A[i][0]
end=A[i][1]
if(dp[start]!=sys.maxint):
for i in range(start,end+1):
dp[end]=min(dp[end],dp[end-i]+1)
return dp[B[1]]``````

• @elmirap Your code is really great! Worked for several cases that I tested. Awesome technique. Btw what is the good source to learn such programming and techniques?
Others who have difficulty understanding the code, run through this example -
List - (0,5) (4,20) (5,15) (5,22) (6,21) (7,12) (9,23) (13,25)
Interval - (6,24)
Ans: 2 which is (5,22) and (13,25)

• @raghujhu true!

• @elmirap Hi, For the below testcase, expected result = 2. However the above code returns 3.
A = [ [0, 4], [4, 6], [7, 9], [5, 9]]
B = [3, 9]
[3,9] is covered by [0,4] and [5,9] (Assumption: These are closed intervals - Both start & end points are inclusive)

• @mohanasundaram your case is wrong. [0, 4] and [5, 9] are not overlap.

• if (start != max) {
start = max;
num++;
}

if (start != max) {
start = max;
num++;
}

Can you please explain why we need if(start!=max)? I feel that this is redundant. Thanks.

• Concise Python. Using Greedy. O(nlogn)

``````def find_min_intervals(intervals, target):
intervals.sort()
res = 0
cur_target = target[0]
i = 0
max_step = 0
while i < len(intervals) and cur_target < target[1]:
while i < len(intervals) and intervals[i][0] <= cur_target:
max_step = max(max_step, intervals[i][1])
i += 1
cur_target = max_step
res += 1
return res if cur_target >= target[1] else 0
``````

• ``````def solve(A,B):
a = sorted(A, key=lambda x: x[0])
print a

prev=None
start = []
end = []
res=0
done = 0
for x, y in a:
if not prev:
prev = (x, y)
start.append(x)
end.append(y)
res+=1
continue
if prev[0] < x < prev[1]:
if y > prev[1]:
end[-1] = y
res+=1
else:
start.append(x)
end.append(y)
if start[-1]<=B[0]<=end[-1] and start[-1]<=B[1]<=end[-1]:
done =1
break
prev = (start[-1], end[-1])
return res if done else 0

print solve([[0,3],[3,4],[4,6],[2,7]],[0,6])
print solve([[0,3],[4,7]],[0,6])
``````

• This post is deleted!

• @leetrocks I think you can solve this problem after you solved all problems in leetcode, actually, leetcode is the good source for you to learn algorithm.

• Sort the interval list A with starting point and then end point. Traverse the list, and skip all the entries
that have end points less than the start point of the target. The results that cover target B are in retVal
There are three conditions to traverse:

1. starting with the current element skip all the elements that have end points less than the end point of current
element.
2. if the end point of next element is greater than current end point and if the start point of next element
is less than or equal to target start point or the end point of last element in retVal list than skip current element. and keep skipping until this condition fails
3. if the last element in the result array has end point greater than the current end point skip the current element.
``````def compareInterval(i1, i2):
if i1[0] == i2[0]:
return -cmp(i1[1],i2[1])
else: return cmp(i1[0],i2[0])

def maxinterval(alist, i):
alist.sort(cmp=compareInterval)
cnt = idx = 0
start = i[0]
retVal = []
print alist
while idx < len(alist):
v = alist[idx]
if retVal and v[0] > retVal[-1][1]: break
if v[1] <= i[0] or (retVal and v[1] <= retVal[-1][1]):
idx += 1
continue
while idx + 1 < len(alist) and v[1] >= alist[idx+1][1] and alist[idx+1][1] < i[1]:
idx += 1
while idx + 1 < len(alist) and alist[idx+1][0] <= start and v[1] <= alist[idx+1][1]:
idx += 1

v = alist[idx]
retVal.append(v)
idx += 1
start = v[1]
if v[1] >= i[1]: break
return len(retVal) if retVal[-1][1] >= i[1] else 0

if __name__ == "__main__":
alist = [[0,5], [4,20], [5,15], [5,22], [6,21], [7,12], [9,23], [13,25]]
interval = [6,24]
print maxinterval(alist,interval)
alist = [[0,3],[3,4],[4,6],[2,7],[2,6]]
interval = [0,6]
print maxinterval(alist,interval)
alist = [[0,3],[4,7]]
interval = [0,6]
print maxinterval(alist,interval)
``````

• @BetaGoGoGo

``````# Given a list of intervals A and one interval B, find the least
# number of intervals from A that can fully cover B.
#
# If cannot find any result, just return 0;
#
# For example:
# Given A=[[0,3],[3,4],[4,6],[2,7]] B=[0,6] return 2 since we can use [0,3] [2,7] to cover the B
# Given A=[[0,3],[4,7]] B=[0,6] return 0 since we cannot find any interval combination from A to cover the B

def findMinIntervals(intervals, target):
"""
:type intervals: List[[int, int]]
:type target: list[int, int]
:rtype: int
"""
intervals.sort()
res = 0
cur_target = target[0]
i = 0
max_step = 0
while i < len(intervals) and cur_target < target[1]:
if intervals[i][0] > cur_target:
return 0

while i < len(intervals) and intervals[i][0] <= cur_target:
max_step = max(max_step, intervals[i][1])
i += 1
cur_target = max_step
res += 1
return res if cur_target >= target[1] else 0

test = [[1,3],[2,4],[3,5],[4,7],[4,9],[7,12]]
target = [2,9]
print(findMinIntervals(test, target), 'should be 2')

test = [[1,3],[5,8],[9,12]]
target = [1,12]
print(findMinIntervals(test, target), 'should be 0')

test = [[1,3],[5,8],[2,13],[9,12]]
target = [1,12]
print(findMinIntervals(test, target), 'should be 2')

test = [[1,13]]
target = [1,12]

print(findMinIntervals(test, target), 'should be 1')

test = [[2,13]]
target = [1,12]

print(findMinIntervals(test, target), 'should be 0')

test = [[1,3],[3,8],[7,12],[2,13]]
target = [1,12]

print(findMinIntervals(test, target), 'should be 2')

``````

• @leili2014 why do we need the first 2 lines under the outer while loop, i.e.

``````if intervals[i][0] > cur_target:
return 0
``````

• Same idea with sorting intervals by start time and greedy.

``````int minCover(vector<pair<int,int>> A, pair<int,int> B) {
sort(A.begin(), A.end());
int endPoint = B.first - 1, startPoint = B.first;
int cnt = 0;
for (int i = 0; i < A.size();) {
if (A[i].first <= startPoint) endPoint = max(A[i++].second, endPoint);
else {
startPoint = endPoint;
++cnt;
if (A[i].first > endPoint || endPoint>= B.second) break;
}
}
return endPoint < B.second ? -1 : cnt;
}
``````

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