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


  • 1
    J

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


  • 0
    M

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

  • 1
    L

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


  • 0
    D

    @raghujhu true!


  • 0
    M

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


  • 0
    C

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


  • 0
    J

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


  • 0

    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
    

  • 0
    S
    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])
    

Log in to reply