@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.
Find least number of intervals from A that can fully cover B


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