关于算法:一文秒杀三道区间集合题目

读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：

1288. 删除被笼罩区间

56. 区间合并

986. 区间列表的交加

———–

常常有读者问区间相干的问题，明天写一篇文章，秒杀三道区间相干的问题。

所谓区间问题，就是线段问题，让你合并所有线段、找出线段的交加等等。次要有两个技巧：

1、排序。常见的排序办法就是依照区间终点排序，或者先依照终点升序排序，若终点雷同，则依照起点降序排序。当然，如果你非要依照起点排序，无非对称操作，实质都是一样的。

2、画图。就是说不要偷懒，勤入手，两个区间的绝对地位到底有几种可能，不同的绝对地位咱们的代码应该怎么去解决。

废话不多说，上面咱们来做题。

区间笼罩问题

这是力扣第 1288 题，看下题目：

题目问咱们，去除被笼罩区间之后，还剩下多少区间，那么咱们能够先算一算，被笼罩区间有多少个，而后和总数相减就是残余区间数。

对于这种区间问题，如果没啥脉络，首先排个序看看，比方咱们依照区间的终点进行升序排序：

排序之后，两个相邻区间可能有如下三种绝对地位：

对于这三种状况，咱们应该这样解决：

对于状况一，找到了笼罩区间。

对于状况二，两个区间能够合并，成一个大区间。

对于状况三，两个区间齐全不相交。

根据几种状况，咱们能够写出如下代码：

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;
}

以上就是本题的解法代码，终点升序排列，起点降序排列的目标是避免如下状况：

对于这两个终点雷同的区间，咱们须要保障长的那个区间在下面（依照起点降序），这样才会被断定为笼罩，否则会被谬误地断定为相交，少算一个笼罩区间。

区间合并问题

力扣第 56 题就是一道相干问题，题目很好了解：

咱们解决区间问题的个别思路是先排序，而后察看法则。

一个区间能够示意为 [start, end]，前文聊的区间调度问题，须要按 end 排序，以便满足贪婪抉择性质。而对于区间合并问题，其实按 end 和 start 排序都能够，不过为了清晰起见，咱们抉择按 start 排序。

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

因为曾经排了序，x.start 很好确定，求 x.end 也很容易，能够类比在数组中找最大值的过程：

int max_ele = arr[0];
for (int i = 1; i < arr.length; i++) 
    max_ele = max(max_ele, arr[i]);
return max_ele;

而后就能够写出残缺代码

# intervals 形如 [[1,3],[2,6]...]
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

区间交加问题

先看下题目，力扣第 986 题就是这个问题：

题目很好了解，就是让你找交加，留神区间都是闭区间。

解决区间问题的思路个别是先排序，以便操作，不过题目说曾经排好序了，那么能够用两个索引指针在 A 和 B 中游走，把交加找进去，代码大略是这样的：

# A, B 形如 [[0,2],[5,10]...]
def intervalIntersection(A, B):
    i, j = 0, 0
    res = []
    while i < len(A) and j < len(B):
        # ...
        j += 1
        i += 1
    return res

不难，咱们先老老实实剖析一下各种状况。

首先，对于两个区间 ，咱们用 [a1,a2] 和 [b1,b2] 示意在 A 和 B 中的两个区间，那么什么状况下这两个区间 没有交加 呢：

只有这两种状况，写成代码的条件判断就是这样：

if b2 < a1 or a2 < b1:
    [a1,a2] 和 [b1,b2] 无交加

那么，什么状况下，两个区间存在交加呢？依据命题的否定，下面逻辑的否命题就是存在交加的条件：

# 不等号取反，or 也要变成 and
if b2 >= a1 and a2 >= b1:
    [a1,a2] 和 [b1,b2] 存在交加

接下来，两个区间存在交加的状况有哪些呢？穷举进去：

这很简略吧，就这四种状况而已。那么接下来思考，这几种状况下，交加是否有什么共同点呢？

咱们惊奇地发现，交加区间是有法则的！如果交加区间是 [c1,c2]，那么 c1=max(a1,b1)，c2=min(a2,b2)！这一点就是寻找交加的外围，咱们把代码更进一步：

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.append([max(a1, b1), min(a2, b2)])
    # ...

最初一步，咱们的指针 i 和 j 必定要后退（递增）的，什么时候应该后退呢？

联合动画示例就很好了解了，是否后退，只取决于 a2 和 b2 的大小关系：

while i < len(A) and j < len(B):
    # ...
    if b2 < a2:
        j += 1
    else:
        i += 1

以此思路写出代码：

# A, B 形如 [[0,2],[5,10]...]
def intervalIntersection(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

总结一下，区间类问题看起来都比较复杂，状况很多难以解决，但实际上通过观察各种不同状况之间的共性能够发现法则，用简洁的代码就能解决。