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)
Find least number of intervals from A that can fully cover 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[endi]+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)

@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)


@elmirap said in Find least number of intervals from A that can fully cover B:
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])

@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: starting with the current element skip all the elements that have end points less than the end point of current
element.  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  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)
 starting with the current element skip all the elements that have end points less than the end point of current