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]-baidu 1point3acres
我们要的是merge个数最少的方法,所以这里应该返回2
https://lina.bitcron.com/post/code/2018-summer-fb-intern-mian-jing
https://zhuanlan.zhihu.com/p/26657786
第二轮我的思路是用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)
我们的目标是去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]-baidu 1point3acres
我们要的是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;
- }
这里有两点说明。第一,其实并不需要全部排序,只需要找出和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)