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


  • 4

    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

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


  • 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