labuladong公众号算法学习笔记 所谓区间问题就是线段问题，合并所有线段、找出线段的交集等。主要有两个技巧： 1、排序 2、画图 画图画图画图。排序排序排序。

区间相关问题

区间覆盖问题区间合并问题区间交集问题总结

区间覆盖问题

可以先算一下，被覆盖区间有多少个，然后和总数相减局势剩余区间数。 区间问题可以首先进行排序，按照区间的起点进行升序排序。可以分为三种情况：情况1、有覆盖区间；情况2、两个区间可以合并成为一个大区间；情况3、两个区间完全不相交。

int removeCoveredIntervals(int[][] intvs){ //按照起点升序排列 Arrays.sort(intvs,(a,b)->{ if(a[0] == b[0]) return b[1]-a[1]; return a[0]-b[0]; }); //记录合并区间的起点和终点 int left = intvs[0][0]; int right = intvs[0][1]; int res = 0; for(int i = 1; i < intvs.length; i++){ int[] intv = intvs[i]; //情况一，找到覆盖区间 if(left <= intv[0]) && right >=intv[1]) res++; //情况二，找到相交区域，合并 if(right >= intv[0] && right <= intv[1]) right = intv[1]; if(right < intv[0]){ left = intv[0]; right = intv[1]; } } return intvs.length - res; }

对于两个起点相同的区间，需要保证长的那个区间在上面（按照终点降序），这样才会被判定为覆盖。

区间合并问题

对于几个相交区间合并后的结果区间x，x.start一定是这些区间中start最小的，x.end一定是这些区间中end最大的。

def merge(intervals): if not intervals: return[] #按照区间的start升序排列 intervals.sort(key = lambda intv:intv[0]) res = [] res.append(intervals[0]) for i in range(1, len(intervals)): curr = intervals[i] #res 中最后一个元素的引用 last = res[-1] if curr[0] <= last[1]: #找到最大的end last[1] = max(last[1],curr[1]); else: #处理下一个待合并区间 res.append(curr); return res;

区间交集问题

思路一般是先排序，然后进行操作。 题目中说已经拍好序了，就可以用两个索引指针在A和B中游走，把交集找出来。 可以先画图，然后分情况进行分析。 没有交集的情况：

if b2 < a1 or a2 < b1: [a1,a2]和[b1,b2]没有交集

存在交集：

if b2 >= a1 and a2 >= b1: [a1,a2]和[b1,b2]有交集

通过画图分析（4中情况）发现交集存在规律，设交集区间为[c1,c2]，则c1 = max(a1,b1) c2 = min(a2,b2)。 指针是否前进取决于a2和b2的大小关系。

def interavalIntersection(A,B): i , j = 0, 0 #双指针 res = [] while i < len(A) and j < len(B): a1, a2 = A[i][0],A[i][1] b1, b2 = B[j][0],B[j][1] #两个区间存在交集 if b2 >= a1 and a2 >= b1: #计算出交集，加入res res.append([max(a1,b1),min(a2,b2)]) #指针前进 if b2 < a2: j += 1 else: i += 1 return res

总结

区间类问题可以通过观察各种不同情况之间的共性发现规律。 可以先按照start升序排列（或者end降序排列）画图找出规律。 然后进行情况分析计算，寻找规律。