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


  • 5
    H

    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


  • 5

    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

  • 7
    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;
    }

  • 2
    G

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


  • 0
    J
    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)

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


  • 2

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

  • 0
    Q
    This post is deleted!

  • 0
    F

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


  • 0
    B

    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)
    

  • 0
    L

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

  • 0
    N

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

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

  • 1
    E

    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;
    }
    

Log in to reply
 

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