一文搞定线段树与扫描线问题

一文搞定区间调度与扫描线问题

1. 扫描线引例:区间调度问题

• 给你输入若干个形如[bein,end]的区间，代表若干个会议的开始时间和结束时间，请你计算至少需要申请多少间会议室

//返回需要申请的会议室数量
int minMeetingRooms(int[][] meetings);

样例分析:meetings= [[0,30],[5,10],[15,20]]，算法应当返回2，因为后面两个会议和第一个会议时间是冲突的，我们至少要申请两个会议室才能让所有会议顺利进行。

如果会议之间的时间存在重叠，那么就需要额外申请会议室来开会，想求至少需要多少间会议室，就是让你计算同一时刻最多有会议在同时进行？换句话说，如果把每个会议的时间占用代价作为一根线段，那么题目就是让你求最多会有几个重叠区间?

对于这种时间安排问题，本质上讲就是区间调度问题，一般来说，第一步是对线段进行排序(排序规则不定)，然后找规律进行解决

2. 贪心算法做时间管理

假设现在 只有一个会议室，但是有若干个会议(区间)，你如何将尽可能将可能多的会议安排到这个会议室?

问题转换一下，就是这个会议室最多能用有几个会议同时进行?

正确的思路分为三步

• 从区间集合intvs中选择一个区间x,这个x是在当前所有区间中结束最早的(end最小):排序
• 把所有与x区间相交的区间从区间集合intvs中删除
• 重复以上两步，直到intvs为空为止，之前选出的那些x就是最大的不相交子集

这个思路的精髓在哪呢?首先很重要的一点是我们的直观推断:如果一个区间的终点比另一个起点要早，那么说明这两个区间必不可能重叠，同时，一个区间的终点肯定是要比起点要晚的，如果我们有一个最早的终点，去与其他区间的起点进行比较，那么就能够得到这些区间是否重叠的结论，一旦我们发现有一个区间与这个最早终点区间不重合，我们就让它迭代为下一次的最早终点区间去和其他区间比较。

如果想要这么做，我们必须保证在比较的时候后者的终点位置是按照次序排好的，为什么不是按照起点位置进行排序呢?这是决定着两个区间是否相交的关键在于终点的位置，前面说过了，判定区间是否重叠的标准是区间的终点是否比起点要早，使用起点是无法得到结论的(可以自己试着推一推，最终落脚点都会回到终点上)。

public int intervalSchedule(int[][] intvs) {
    if (intvs.length == 0) return 0;
    // 按 end 升序排序
    Arrays.sort(intvs, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return a[1] - b[1];
        }
    });
    // 至少有一个区间不相交
    int count = 1;
    // 排序后，第一个区间就是 x
    int x_end = intvs[0][1];
    for (int[] interval : intvs) {
        int start = interval[0];
        if (start >= x_end) {//起点比终点要晚,这必不重叠
            // 找到下一个选择的区间了
            count++;
            x_end = interval[1];
        }
    }
    return count;
}

3. 剪视频检出一个贪心算法

• 给你若干个较短的视频片段和一个较长的视频片段，请你从较短的片段中尽可能少地跳出一些片段，拼接出较长的这些片段

你将会获得一系列视频片段，这些片段来自于一项持续时长为time秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。

甚至可以对这些片段自由地再剪辑：

例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/video-stitching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 区间问题是肯定按照区间的起点或者终点进行排序的，排序决定于问题的性质，这是因为排序之后更容易找到相邻区间之间的联系，如果是求最值的问题，可以使用贪心算法进行求解

好了回到题目上，这个题目要求我们用最小的视频片段拼接出最长的完整片段，遇到求最值问题，思考是否能够进行贪心

• 如果要用若干短视频拼接出视频[0,T]，至少需要有一个视频的起点是0
• 如果有几个短视频的起点都相同，那么肯定选择结束时间最晚的那个片段（不要白不要）

好了基于上面的思路，如果我们要做这个合并区间的话，落脚点是在起点的，在起点的基础选择终点，那么这就是我们第一步排序的依据。将clips按照起点升序排序，起点相同的按照终点降序排序。

然后与时间管理那道题一样，寻找下一个迭代区间作为下一个视频片段，时间管理中选择的是下一个不重叠的区间，这道题也是一样的，由于我们是一个贪心的选择策略，那么就是

实现代码如下

public int videoStitching(int[][] clips, int time) {
    //1.排序:按照起点进行排序,从小到大
    Arrays.sort(clips, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];
        }
    });
    //2.依据规律来进行区间的合并
    int ans = 0;//选择的短视频个数
    int curEnd = 0;//curEnd表示的是已选择的视频片段的所构成的片段的终点
    int nextEnd = 0;//一开始啥也没选,必然是0
    int i = 0;
    while (i<clips.length && clips[i][0] <= curEnd){//这里本来在循环之前要做一步的,这里省略,如果最早的起点都不是0,那么肯定弄不了
        while (i<clips.length && clips[i][0] <= curEnd){//在这个区间上进行贪心,当起点要小于它的终点的时候,证明还能选
            nextEnd = Math.max(nextEnd,clips[i][1]);
            i++;
        }
        curEnd = nextEnd;
        ans++;
        if(curEnd >= time){
            return ans;
        }
    }
    return -1;
}

• 这里的话讲一下这一句条件i<clips.length && clips[i][0] <= curEnd

首先我们知道curEnd是当前拼接出来的视频片段的终点,那么什么时候迭代，什么时候继续在这个区间选呢?

可以选的条件的是当起点最早，被合并区间有重叠而最晚的终点还没有确定的时候，这时候可以继续选，那么体现到代码上就是:当前起点比拼接出来的视频长度终点要早,那么就说明还在重叠区间内,它还在挑最大的终点,一旦发现起点要比之前拼出来的视频片段还要大了,说明没有重叠区间了,迭代到下一次贪心选择。

4. 区间三兄弟

做区间问题，要记住两个步骤

• 排序
• 画图:画图的目的是为了穷举出区间与区间之间的关系，便于我们更好制定解题策略

4.1 区间覆盖问题

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-covered-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 这题目是问我们被覆盖区间会有多少个，然后和总数相减就是剩余的区间数

对于这种问题，如果没有头绪的话可以先排个序看看，比如我们按照区间的起点进行升序排序

排序之后有三种情况:完全不重叠、部分重叠、完全重叠(覆盖)

依据这几种情况，我们先写出代码

完全不重叠，不管他，跳过

部分重叠，则合并为一个大区间

完全重叠，找到了覆盖区间，标记它

public int removeCoveredIntervals(int[][] intervals) {
    //对起点进行排序哈,从小到大,起点相同时按照降序排序
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[0] == o2[0]){
                return o2[1]-o1[1];
            }
            return o1[0]-o2[0];
        }
    });
    //记录合并区间的起点和终点
    int left = intervals[0][0];
    int right = intervals[0][1];
    int ans = 0;
    for(int i = 1;i<intervals.length;i++){
        int intv[] = intervals[i];
        //情况1:我们找到一个覆盖区间
        if(left<=intv[0] && right>=intv[1]){
            ans++;
        }
        //情况2:找到一个相交的区间,重叠的(也就是这个区间的起点比对标区间的终点要早)
        //right<=intv[1]是限制重叠这种状态,避免去到了覆盖
        if(right>= intv[0] && right<=intv[1]){
            right = intv[1];
        }
        //情况3:完全不相交,证明能合并的,能覆盖的都覆盖完了,去下一次贪心选择
        if(right < intv[0]){
            left = intv[0];
            right = intv[1];
        }
    }
    return intervals.length-ans;
}

4.2 区间合并问题

对于区间合并问题而言，其实按照end和start排序均可以，前面的时间管理问题是为了满足贪心的性质才有要求end排序的。

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于区间合并，首先就是他们是重叠的，在此基础上，选择起点最早的，终点最晚的就是它们合并之后的结果

public int[][] merge(int[][] intervals) {
    List<int[]> res = new ArrayList<>();
    if(intervals == null || intervals.length ==0){
        return new int[0][];
    }
    //首先按照起点进行排序
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];//如果大于0则换位置,那么就是从小到大排序
        }
    });
    int[] cur = intervals[0];
    for (int i = 1;i<intervals.length;i++) {//这里index从1开始也行
        int[] next = intervals[i];
        if(cur[1] >= next[0]){//如果下一个区间的startTime是比当前的endTime要小的话,那么就是证明有重合区间
            cur[1] = Math.max(cur[1],next[1]);//这时候将endTime给取出来,取较大值
        }else{//否则的话就是没有交集了,要迭代到下一次选择中去
            res.add(cur);
            cur = next;
        }
    }
    //要注意,这个for结束的时候是根据next结束之后来break的
    //所以无论如何,最后一个cur都没有被加入到ans中
    res.add(cur);
    return res.toArray(new int[0][]);
}

4.3 区间交集问题

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/interval-list-intersections
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 题目的要求就是然你找交集，注意区间都要是是闭区间，由于涉及到两个区间，那么我们可以用双指针技巧，让它们在A和B中游走，将交集找出来。

注意，尽管有点数组+双指针的感觉，但是区间问题仍然是要通过画图找出其相对位置关系的

对于两个区间，用[a1,a2]和[b1,b2]来表示在A和B中的两个区间，那么什么情况下这两个区间没有交集呢

对于一维的两个区间而言，只有这两种情况，也就是

if(b2<a1 || a2<b1){
    return "没有交集";
}

if(b2>=a1 && a2>=b1){
    return "有交集";
}

对于交集[c1,c2]，交集区间的起点是c1 = max(a1,b1),c2=min(a2,b2)，到这里我们可以先写出选择交集的伪代码了

while(i < A.length && j<B.length){
    a1,a2 = A[i][0],A[i][1];
    b1,b2 = B[i][0],B[i][1];
    if(b2>=a1 && a2>=b1){//有交集
        res.add(new int[]{max(a1,b1),min(a2,b2)});
    }
}

最后一步，确认双指针前进的策略，那么我们只需要确认a2和b2的大小就好了，为什么呢?

这是因为交集有没有结束取决于终点较晚的那一个区间，如果那个区间没有结束，那么就有可能有交集存在。

public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    //1.排序,已经做好了,只需要双指针即可
    List<int[]> list = new ArrayList<>();//都是从尾部插入,数组的最快了
    int p1 = 0,p2 = 0;
    while (p1<firstList.length && p2<secondList.length){
        //如果有交集
        int a1 = firstList[p1][0],a2=firstList[p1][1];
        int b1 = secondList[p2][0],b2=secondList[p2][1];
        if(b2>=a1 && a2>=b1){
            list.add(new int[]{Math.max(a1,b1),Math.min(a2,b2)});
        }
        if(b2 < a2){
            p2++;
        }else{
            p1++;
        }
    }
    return list.toArray(new int[0][]);
}

5.扫描线技巧:合理申请会议室

给你输入若干的时间区间，给你任意一个时刻，你是否能够说出这个时刻有几个会议?

我们将时间线想象成一个初始值为0的数组，每个时间区间[i,j]就相当于一个子数组，这个时间区间有一个会议，那么我就把这个子数组中的元素都加1，如果有会议退出了，那么我就把这个数组的元素都减1

最后，我们就能够知道每个时刻都有几个会议了，如果想要求至少需要多少间会议室，那么我只需要求的过程中取一个max就好了

我们首先把这些会议的时间区间进行投影

上图:红色的点代表着每个会议开始的时间点，绿色的点代表每个会议的结束时间点

现在假想有一条带着计数器的线，在时间上从左到右扫描，每遇到红色的点，计数器count+1，每遇到绿色的点，计数器count-1

对区间进行投影，就相当于对每个区间的起点和终点分别进行排序

int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] begin = new int[n];
    int[] end = new int[n];
    // 把左端点和右端点单独拿出来
    for(int i = 0; i < n; i++) {
        begin[i] = meetings[i][0];
        end[i] = meetings[i][1];
    }
    // 排序后就是图中的红点
    Arrays.sort(begin);
    // 排序后就是图中的绿点
    Arrays.sort(end);

    // ...
}

然后扫描线从左向右前进，遇到红点就计数器+1，否则-1

int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] begin = new int[n];
    int[] end = new int[n];
    for(int i = 0; i < n; i++) {
        begin[i] = meetings[i][0];
        end[i] = meetings[i][1];
    }
    Arrays.sort(begin);
    Arrays.sort(end);

    // 扫描过程中的计数器
    int count = 0;
    // 双指针技巧
    int res = 0, i = 0, j = 0;
    while (i < n && j < n) {
        if (begin[i] < end[j]) {
            // 扫描到一个红点
            count++;
            i++;
        } else {
            // 扫描到一个绿点
            count--;
            j++;
        }
        // 记录扫描过程中的最大值
        res = Math.max(res, count);
    }
    
    return res;
}

6. 经典难题:矩形的并

我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。

计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。

返回 总面积 。因为答案可能太大，返回 109 + 7 的 模 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/rectangle-area-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

假设我们有一根竖直的扫描线，从左到右扫描区间

然后我们让这根竖线向右移动，一直移动直到遇到下一根竖线为止，如图所示

我们一直向右扫，直到把这个矩形给扫完

这是从左到右的一种模拟思路，如果我们选择从下往上扫，那么就可以看做一个容器(二维)里倒水，水慢慢往上涨，最后算一下倒进去多少水就可以得到矩形面积了

从上面的分析可以知道，无论我们选择从左到右扫，还是选择从下到上来扫，具有下面的特点

• 扫描线的长度是一直在变动的：你或许会被上边的图所误导，认为扫描线是两边无限延伸的直线，实际上是根据当前扫描的矩形的边长所限制的一根线段。

我们可以把扫描线看作为一根无限长的和y轴平行的数轴，并赋予每个坐标一个属性cover代表有多少个矩形覆盖在这个坐标上。每次碰到一个矩形的左边后，我们让这个矩形覆盖的坐标的cover++，每次碰到一个矩形的右边后，我们让这个矩形覆盖的坐标的cover--

那么我们发现，在计算这些面积的时候实际上就是在不断维护区间，既然是区间维护的问题，我们可以引入线段树来优化算法

线段树简介:所谓线段树就是将单一一个区间端点坐标作为叶子节点，然后维护区间也就是将这若干个节点合并为一个父节点。

• 那么我们就可以对y轴建立一棵线段树来维护扫描树了
• 扫描线每次碰一次边，就投影到y轴的线段树上进行操作

当然了这是一种优化的算法，我们能力有限还是待日后再来优化吧

先来讲讲最简单的解决办法

我们将矩形分为出边和入边，依照上图所示，左边这根线就是入边，我们将其记录下来

右边那根使得扫描线要发生变化的边，我们记录为出边，同时也是下一个矩形的入边

然后呢相邻线段之间的宽度为单个矩形的宽度，这个的话可以通过x的差值直接算出来，同时直接转换为求该区间内高度的并集，这样的话就转化成了一维上的区间调度问题了

来看看解法

public int rectangleArea(int[][] rectangles) {
    //1.首先搞清楚rectangle是[x1,y1,x2,y2]
    //然后咱们把矩形按照x进行排序,从小到大,先把x拿出来
    List<Integer> xes = new ArrayList<>();
    for (int[] rectangle : rectangles) {
        xes.add(rectangle[0]);
        xes.add(rectangle[2]);
    }
    Collections.sort(xes);
    for(int i = 1;i<xes.size();i++){
        //2.计算出宽度,取出端点
        int front = xes.get(i-1);//线段的起始端点
        int backend = xes.get(i);//线段的结束端点
        int len = backend-front;
        if(len == 0){
            continue;//宽度为0,没有计算价值
        }
        //然后计算所有在这个x范围的内矩形,我们先把y给它给拿进来
        List<int[]> lines = new ArrayList<>();//这个代表着在区间里面,所有的y线段
        for (int[] rectangle : rectangles) {
            //首先搞清楚rectangle是[x1,y1,x2,y2]
            //x1是左下角
            //x2是右上角
            //然后找出来所有和x有交集的
            if(rectangle[0]<= front && rectangle[2]>= backend){
                //我们将这一段y给加入到候选区间中
                lines.add(new int[]{rectangle[1],rectangle[2]});
            }
        }
        //然后就开始转化为了`区间合并问题了`
    }
    return 0;
}

我们来看看上面这一段代码在干啥，其实很简单:

• 给矩形的最左边起始端点进行排序，从小到大哈
• 然后取出这些端点,形成宽度线段,待计算
• 然后找出矩形与这些宽度区间相交的y线段

下一步就是将这些y线段进行合并了，合并的思路参考区间三兄弟的区间合并问题

    //然后就开始转化为了`区间合并问题了`
    if(lines.size() == 0){
        continue;
    }
    int[][] intervals = lines.toArray(new int[0][]);
    //首先按照起点进行排序
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];//如果大于0则换位置,那么就是从小到大排序
        }
    });
    long total = 0;
    int[] cur = intervals[0];
    for(int j = 0;j<intervals.length;j++){
        int[] next = intervals[j];
        if(cur[1] >= next[0]){
            cur[1] = Math.max(cur[1],next[1]);
        }else{
            total += cur[1] - cur[0];
            cur = next;
        }
    }
    total += cur[1] - cur[0];
    ans += total*len;
    ans %= MOD;
}

以上就是这道题的解法了

来看看我们oj上的这道题

这道题是一模一样的，只是我们要处理一下输入类型就好了

package leetcode_3;

import java.util.*;

public class RectangleArea {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double[][] rectangles = new double[n][4];
        for (int i = 0; i < n; i++) {
            double x1 = scanner.nextDouble(),y1 = scanner.nextDouble(),x2 = scanner.nextDouble(),y2= scanner.nextDouble();
            rectangles[i][0] = x1;
            rectangles[i][1] = y1;
            rectangles[i][2] = x2;
            rectangles[i][3] = y2;
        }
        double ans = rectangleArea(rectangles);
        System.out.println(String.format("%.2f",ans));
    }

    public static int MOD = (int)1e9+7;
    public static double rectangleArea(double[][] rectangles) {
        //1.首先搞清楚rectangle是[x1,y1,x2,y2]
        //然后咱们把矩形按照x进行排序,从小到大,先把x拿出来
        double ans = 0;
        List<Double> xes = new ArrayList<>();
        for (double[] rectangle : rectangles) {
            xes.add(rectangle[0]);
            xes.add(rectangle[2]);
        }
        Collections.sort(xes);
        for(int i = 1;i<xes.size();i++){
            //2.计算出宽度,取出端点
            double front = xes.get(i-1);//线段的起始端点
            double backend = xes.get(i);//线段的结束端点
            double len = backend-front;
            if(len == 0){
                continue;//宽度为0,没有计算价值
            }
            //然后计算所有在这个x范围的内矩形,我们先把y给它给拿进来
            List<double[]> lines = new ArrayList<>();//这个代表着在区间里面,所有的y线段
            for (double[] rectangle : rectangles) {
                //首先搞清楚rectangle是[x1,y1,x2,y2]
                //x1是左下角
                //x2是右上角
                //然后找出来所有和x有交集的
                if(rectangle[0]<= front && rectangle[2]>= backend){
                    //我们将这一段y给加入到候选区间中
                    lines.add(new double[]{rectangle[1],rectangle[3]});
                }
            }
            //然后就开始转化为了`区间合并问题了`
            if(lines.size() == 0){
                continue;
            }
            double[][] intervals = lines.toArray(new double[0][]);
            //首先按照起点进行排序
            Arrays.sort(intervals, new Comparator<double[]>() {
                @Override
                public int compare(double[] o1, double[] o2) {
                    return (int)(o1[0]-o2[0]);
                }
            });
            long total = 0;
            double[] cur = intervals[0];
            for(int j = 0;j<intervals.length;j++){
                double[] next = intervals[j];
                if(cur[1] >= next[0]){
                    cur[1] = Math.max(cur[1],next[1]);
                }else{
                    total += cur[1] - cur[0];
                    cur = next;
                }
            }
            total += cur[1] - cur[0];
            ans += total*len;
        }
        return ans;
    }
}