Massive Algorithms: Find min merge intervals

https://www.1point3acres.com/bbs/thread-224128-1-1.html给定一堆interval（如果我们管这个list叫IntervalList），和一个target interval
我们的目标是去merge这些interval，让merge的结果能够『cover』这个target interval，求这种merge所需的原interval的最少个数是多少

有点抽象，举个栗子
IntervalList: [-1, 9] [ 1, 10] [ 0, 3] [ 9, 10] [ 3, 14] [ 2, 9] [10, 16]
target interval: [ 2, 15]
在这个栗子中，我们发现要想cover[2,15]有好几种方法，比如：
[-1, 9] + [ 9, 10] + [10, 16] 或者 [ 1, 10] + [10, 16]
我们要的是merge个数最少的方法，所以这里应该返回2
https://lina.bitcron.com/post/code/2018-summer-fb-intern-mian-jing

 public int minCover( List<Interval> list, Interval target){
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    Collections.sort(list, new Comparator<Interval>(){
        public int compare(Interval a,Interval b){
        if(a.start-b.start==0) return a.end-b.end;
        return a.start-b.start;
        }
    });
    int res = 0;
    for(Interval i :list){
        if(i.end>=target.start&&i.start<=target.start){
            map.put(i.end,1);
        }
        else if(i.start>target.start){
            int min = Integer.MAX_VALUE;
            for(int k = i.start;k<=Math.min(target.end,i.end));k++){
                if(map.containsKey(k)) min = Math.min(min,map.get(k));
            }
            if(min!=Integer.MAX_VALUE)  map.put(i.end,min+1);
        }
        if(map.containsKey(i.end)&&i.end>=target.end)res = Math.min(res,map.get(i.end));
    }
    return res;
 }

感觉第二轮的题更像是greedy。先把所有intervals按start排序，然后遍历。首先我们要从那些start小于等于target.start的intervals中选end最大的那个，假设我们用A来表示那个选出来的interval。如果A.end小于target.end，我们就得继续遍历，从那些start小于等于A.end的intervals中选end最大的那个。最终返回所选的interval个数。时间复杂度是O(nlogn)。隐约觉得很像jump game II。

层主考虑下特殊情况，所有区间都比target区间大，这样的话层主的第一个loop是跳不出来的

有道理！不过这样就没有答案了诶。那就在loop前加一行判断好了！

public int find(Interval[] intervals, Interval target){
if(intervals == null || intervals.length == 0) return -1;
Arrays.sort(intervals, new Comparator<Interval>(){
public int compare(Interval a, Interval b){
return a.start - b.start;
}
});
int res = 0;
int i = 0;
int start = target.start;
while(i < intervals.length){
int cur = greedy(intervals, i, start);
res++;
if(intervals[cur].end >= target.end) return res;
i = cur;
start = intervals[cur].end;
}
return -1;
}
public int greedy(Interval[] intervals, int i, int tar){
int res = i;
while(i < intervals.length){
if(intervals[i].start <= tar && intervals[i].end > intervals[res].end){
res = i;
}else if(intervals[i].start > tar) return res;
i++;
}
return res;
}

https://zhuanlan.zhihu.com/p/26657786

这里有两点说明。第一，其实并不需要全部排序，只需要找出和target有overlap的interval进行排序。第二，关于greedy。在inner while loop里面，我们所需要找的，就是满足start比cur_target要小的interval中，end最大的那个。这样去最大的end可以让加入的这个interval，最有价值，延展到最远。一开始的cur_target是target的start，后面的cur_target就是上一个加入的interval的end(为了保持区间不中断)。

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

第二轮我的思路是用DP做
先将IntervalList按找start排序O(nlgn)
再设立Dp方程
DP代表了对于第i个interval[curStart, curEnd]，想要达到[targetStart, curEnd]所需要merge的个数

补充内容 (2017-1-25 12:20):
转换方程就是对于dp，我们去遍历之前所有的dp状态，尝试去与之前的interval去和当前的inreval进行一次merge，如果能merge，dp就可能可以更新为dp[j] + 1

补充内容 (2017-1-25 12:24):
最终再遍历一次dp，看下curEnd是否大于targetEnd，如果是的话，就可以去更新最终的答案了
（直接也应该对达不到targetStart的interval进行特殊处理）
这样最终的复杂度是O（n^2)

Find min merge intervals - Facebook

Labels

Popular Posts