【九章算法强化班】课程笔记2——扫描线

扫描线

lintcode391. 数飞机

题目

给出飞机的起飞和降落时间的列表，用 interval 序列表示. 请计算出天上同时最多有多少架飞机？

样例

对于每架飞机的起降时间列表：[[1,10],[2,3],[5,8],[4,7]], 返回3。

分析

计算空中的飞机个数，可以看成用一个线从左到右扫描的过程，计算每一时刻空中飞机的数量。

优化：只计算所有线段起始位置时天上的飞机即可，因为只有起始点是可能发生变化的点。遇到起点，天上的飞机数+1，遇到终点则-1。

因此，我们先将所有线段的起点、终点排序，并标记是起点还是终点，然后从小到大遍历这些点，遇到起点则+1，遇到终点-1，返回过程中最大的数值即为空中飞机数的最大值。

需要注意的是：在同一点上会同时有开始点和结尾点，此时应该把结尾点放在前面，否则会出现多计算的情况。

代码

import com.sun.org.apache.xpath.internal.operations.Bool;
import java.util.*;
public class airplane_count {
    //Definition of Interval:
    public class Interval{
        Integer start, end;
        Interval(Integer start, Integer end) {
            this.start = start;
            this.end = end;
        }
    }

    //Definition of node:
    public class Node implements Comparable<Node> {
        Integer val;
        boolean isstart;
        Node(Integer val, boolean isstart) {
            this.val = val;
            this.isstart = isstart;
        }
        //定义排序接口
        public int compareTo(Node Other) {
            if(this.val == Other.val){//如果连个节点位置相同，把结束点排在前面
                return Boolean.compare(this.isstart,Other.isstart);
            }
            else{
                return Integer.compare(this.val, Other.val);
            }
        }
    }

    public int countOfAirplanes(List<Interval> airplanes) {
        int count = 0;
        int max = 0;
        int size = airplanes.size();
        // write your code here
        //插入元素
        Node[] array = new Node[2 * size];
        for (int i = 0; i < airplanes.size(); i++) {
            array[2 * i] = (new Node(airplanes.get(i).start, true));
            array[2 * i + 1] = (new Node(airplanes.get(i).end, false));
        }
        //排序
        Arrays.sort(array);
        //遍历
        for (int i = 0; i < array.length; i++) {
            if (array[i].isstart) {
                count++;
                if (count > max) {
                    max = count;
                }
            } else {
                count--;
            }
        }
        return max;
    }
}

252.Meeting Rooms

题目

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

思路

题目是说判断一个人是否可以参加给出的所有的会议，可以沿用扫描线的思路：同一时刻最多只有一个会议正在召开，就可以参加所有会议。

还有另外一种更快的思路：

如果每一个会议的开始都在上一个会议结束之后，那么就不会有时间冲突的会议，就可以都参加了，所以可以将给出的所有会议的开始时间和结束时间分别放入两个数组中，分别排序，然后判断是否所有的时间满足：starts[i]>ends[i-1]。

代码

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
            public boolean canAttendMeetings(Interval[] airplanes) {
        int count = 0;
        // write your code here
        int[] starts = new int[airplanes.length];
        int[] ends = new int[airplanes.length];

        //插入元素
        for (int i = 0; i < airplanes.length; i++) {
            starts[i] = airplanes[i].start;
            ends[i] = airplanes[i].end;
        }
        //排序
        Arrays.sort(starts);
        Arrays.sort(ends);

        //遍历
        for (int i = 1; i < starts.length; i++) {
            if (starts[i]<ends[i-1]) {
                return false;
            }
        }
        return true;
    }
}

253.Meeting Rooms II

题目

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

给定一系列会议的开始和结束时间，返回所需的最大会议室数量

分析

方法一：

用扫描线模拟扫描过程，计算扫描线最多同时扫描几个区间。

方法二：

分别对会议开始和结束的时间排序，两个指针ij分别指向开始数组和结束数组，当start[i] < end[j]时，i++;sum++;

否则j++,记录最大的sum。

代码

方法一：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    class Node{
        int time;
        boolean isStart;
        Node(int time,boolean isStart){
            this.time = time;
            this.isStart = isStart;
        }
    }
    public int minMeetingRooms(Interval[] intervals) {
        Comparator<Node> tmp = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.time != o2.time) return o1.time - o2.time;
                else{
                    if(o1.isStart == true){
                        return 1;
                    }
                    else return -1;
                }
            }
        };
        PriorityQueue<Node> heap = new PriorityQueue<>(tmp);
        for(int i = 0 ; i < intervals.length;i++){
            heap.add(new Node(intervals[i].start,true));
            heap.add(new Node(intervals[i].end,false));
        }
        int max = 0;
        int sum = 0;
        while(!heap.isEmpty()){
            if(heap.poll().isStart){
                sum++;
                max = Math.max(max,sum);
            }
            else {sum--;}
        }
        return max;
    }
}

方法二：

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MeetingRoomsII {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];

        for(int i = 0 ; i < intervals.length;i++){
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int max = 0;
        int sum = 0;
        int j = 0;
        int i = 0;
        while(i < starts.length && j < ends.length){
            if(starts[i] < ends[j]){
                sum++;
                i++;
                max = Math.max(max,sum);
            }
            else {
                j++;
                sum--;
            }
        }
        return max;
    }
}

218.The Skyline Problem

题目

---

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of “key points“ (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

题目给定每一个建筑的起始结束位置和其高度，返回建筑物构成的轮廓的拐点坐标。

分析

根据观察，可以用扫描线的思路解决。

首先需要将建筑物的开始和结束节点及其对应的高度加入堆heap中，按照坐标从小到大进行排序，当坐标一致的时候，将结束点排在前面。

另外，还需要一个堆heightTemp来维护当前扫描线扫过的建筑的高度，以便迅速知道当前的最大高度。

接下来，将节点依次出堆模拟扫描线扫描的过程，分下面两种情况：

1. 遇到起始点:
   1. 该点的高度大于当前最大高度，需要将该点坐标以及高度加入结果集，同时将高度加入heightTemp
   2. 该点的高度不大于当前最大高度，则只需将该点高度加入heightTemp，无需加入结果集。
2. 遇到结束点：
   1. 该点高度就是当前最大高度，则需要将最大高度从heightTemp中pop出去，然后将该点坐标和pop之后的当前最大高度加入结果集。
   2. 该点高度小于当前最大高度，只需将该点高度从heightTemp中pop出去。

实现上面的算法之后，还不够，因为忽略了在同一个位置有多个点出现的情况，比如某个位置即是A建筑的结束也是B建筑的开始位置，将它们都加入的结果集，显然是重复的，需要筛选掉只剩一个，分如下两种情况：

1. 在某个点有多个建筑结束 —> 取最后一个结束的，也就是高度最低的
2. 在某个点有多个建筑开始 —> 取高度最高的
3. 在某个点既有建筑开始也有建筑结束，但前后高度不一样 —> 取开始高度最高的
4. 在某个点既有建筑开始也有建筑结束，但前后高度一样 —> 不加入最终结果集

基于上面的思路，可以开始写代码了

据说这道题还可以用线段树做，待学习。。。

代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class TheSkylineProblem {
  //节点，包含坐标，高度，开始点or结束点
    class Node{
        int loc;
        int height;
        boolean isStart;
        Node(int loc,int height,boolean isStart) {
            this.loc = loc;
            this.height = height;
            this.isStart = isStart;
        }
    }

    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
      //Node堆，排序依据：坐标小的优先，坐标相同的结束点优先，起始和结束相同的高度高的优先。
       Comparator<Node> cmp = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.loc != o2.loc)return o1.loc - o2.loc;
                else {
                    if(o1.isStart == o2.isStart){
                        return o1.height - o2.height;
                    }
                    else {
                        if(o1.isStart==true){
                         return -1;
                        }
                        else return 1;
                    }
                }
            }
        };
	//最大堆，用于存放扫描线扫过的建筑的高度
        Comparator<Integer> MaxCmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        };
      //堆声明
        PriorityQueue<Node> heap = new PriorityQueue<>(cmp);
        PriorityQueue<Integer> heightTemp = new PriorityQueue<>(MaxCmp);
      //将给定数据点入堆
        for(int i = 0;i < buildings.length;i++){
            heap.add(new Node(buildings[i][0],buildings[i][2],true));
            heap.add(new Node(buildings[i][1],buildings[i][2],false));
        }
      //数据点出堆，模拟扫描过程
        while (!heap.isEmpty()){
            Node node = heap.poll();//出堆
            //是开始节点
            if(node.isStart){
                //如果高于当前最大高度，将坐标和对应高度加入结果集，同时标记为开始节点
                if(heightTemp.isEmpty() || node.height > heightTemp.peek()){
                    result.add(new int[]{node.loc,node.height,1});
                    heightTemp.add(node.height);
                }
              //如果没有高于当前最大高度，仅加入当前高度对，不加入结果集
                else {
                    heightTemp.add(node.height);
                }
            }
            //是结束节点
            else {
                //如果该节点对应的高度就是当前最大高度
                if(!heightTemp.isEmpty() && node.height == heightTemp.peek()){
                    //将最大高度从当前高度堆中弹出
                    heightTemp.poll();
                    if(heightTemp.isEmpty()){
                        //结果集中加入当前剩余的最大高度
                        result.add(new int[]{node.loc,0,0});
                    }
                    else {
                        //结果集中加入当前剩余的最大高度
                        result.add(new int[]{node.loc,heightTemp.peek(),0});
                    }
                }
                //如果该节点对应的高度小于当前最大高度，则将该高度从当前高度对中移除
                else {
                    heightTemp.remove(node.height);
                }
            }
        }
      //对结果集中节点进行处理，主要处理两种情况:
      //1.同一位置有多个点，包括开始点和结束点
      //2.在某一位置，有结束点和开始点，但前后高度一样
        List<int[]> result2 = new ArrayList<>();
        int i = 0;int j = 0;
        while(i < result.size() && j < result.size()){
            int maxTemp = result.get(i)[1];
          //相同位置有多个节点情况
            while (j < result.size() && result.get(i)[0] == result.get(j)[0]){
                //在结束节点中选最低的
                if(result.get(j)[2] == 0){
                    maxTemp = Math.min(maxTemp,result.get(j)[1]);
                }
                //在开始节点中选最高的
                else {
                    maxTemp = Math.max(maxTemp,result.get(j)[1]);
                }
                j++;
            }
          //如果跟前一个高度不一致，才加入最终结果集
            if(result2.isEmpty() || result2.get(result2.size()-1)[1] != maxTemp){
                result2.add(new int[]{result.get(i)[0],maxTemp});
            }
            i = j;
        }
      //返回最终结果集
        return result2;
    }
}