Minimum number of Intervals to cover the Target Interval O(n) solution


  • 3

    Any ideas please share and appreciate that.

    Interview question, hope to help.
    Choose from a list of intervals, to make full coverage of target interval with minimum selection. If cannot cover, return -1.
    for example: [[3,6],[4,5],[7,10],[6,9],[7,12],[12,17],[10,13],[18,22],[16,18]]; target is [7, 22]; should return 3;

    here is my solution, with O(n) time and O(n) space. The idea is similar to LeetCode 45. Jump Game II. The tricky part is how to find the starting point to just cover the target.start. Basically, it is a Greedy question. I used the "sweep line" like method to build an auxiliary array to mimic the Jump Game.

    public class MinimumCoverInterval {
    	public int minimumCoverInterval(Interval[] intervals, Interval target) {
    		if (intervals == null || intervals.length == 0) return 0;
    		int min = Integer.MAX_VALUE;
    		int max = 0;
    		for (Interval i : intervals) {
    			min = Math.min(min, i.start);
    			max = Math.max(max, i.end);
    		}
    		int[] count = new int[max - min + 1];
    		for (Interval i : intervals) {
    			count[i.start - min] = Math.max(count[i.start - min], i.end - i.start);
    		}
    
    		int reach = 0;
    		int maxReach = 0;
    		int target_start = target.start - min;
    		int target_end = target.end - min;
    		int i = 0;
    		for (; i <= target_start; i++) {
    			if (i + count[i] < target_start) continue;
    			reach = Math.max(reach, i + count[i]);
    		}
    		int res = 1;
    		for (; i < count.length; i++) {
    			if (reach >= target_end) break;
    			maxReach = Math.max(maxReach, i + count[i]);
    			if (reach <= i) {
    				reach = maxReach;
    				res++;
    			}		
    		}
    		return reach >= target_end ? res : -1;
    	}
    }
    

  • 1
    /**
    Based on your example, it seems the input interval array is not sorted.
    Sort the array of interval objects first. Then do a O(n) tarversal to find the minimum intervals needed for coverage.
    Time complexity:O(nlogn) where n is the size of the input array of intervals.
    **/
    public class IntervalComparator<Interval> implements Comparator{
    	public int compare(Interval a, Interval b){
    		if(a.start == b.start){
    			return a.end - b.end;
    		}
    		return a.start - b.start;
    	}
    
    }
    
    public int minCover(Interval[] arr,Interval target){
    	Arrays.sort(arr,new IntervalComparator());
    	int i = 0;
    	while(i < arr.length){
    		if(arr[i].end < target.start){
    			i++;
    		}
    	}
    	
    	int count = 0;
    	while(target.start <= target.end){
    		Interval best = null;
    		while(i < arr.length && arr[i].start <= target.start){
    			if(best == null || arr[i].end > best.end){
    				best = arr[i];
    				i++;
    			}
    		}
    		if(best == null){
    			return -1;
    		}
    		count++;
    		target.start = best.end + 1;
    	}
    	return count;
    }

  • 0
    F

    @divyam01986 your solution has some problem regarding following test case:

    (0,3) (4,7), target is (0,7), I think it should output 0, but your algorithm output 2.


  • 1
    X

    Same as jump game II

    Arrays.sort(list, new Comparator<Interval>(){
    			public int compare(Interval a, Interval b) {
    				if (a.start != b.start) {
    					return a.start - b.start;
    				}
    				return a.end - b.end;
    			}
    		});
    		
    		int num = 0, i = 0, start = interval.start, end = -1;
    		while (i < list.length) {
    			if (list[i].end <= start) {
    				i++;
    			} else {
    				if (list[i].start > start) break;
    				while (i < list.length && list[i].start < start) {
    					end = Math.max(end, list[i].end);
    					i++;
    				}
    				if (start != end) {
    					num++;
    					start = end;
    				}
    			}
    		}
    		
    		if (end < interval.end)
    			return 0;
    		return num;
    

  • 0
    A

    @sheva It's a nice solution but it ain't O(n) time/space. The size of your count array is dependent on the ranges of the input intervals. E.g. if you're given a single interval [1,1M], you'll end up with 1M time and space.
    The only way I see to avoid it is to keep that values in a sorted map, but that will cost you O(nlogn) for the insertions.


Log in to reply
 

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