算法-扫描线

1. 经典扫描线

经典问题:数飞机问题

给一些飞机飞行的时间区间。求天上最多有多少个飞机同时在飞。

例如给

1
2
3
4
5
[1,3]
[2,4]
[5,6]
求天上同时有多少架飞机

思路一,细粒度扫描

遍历每个时刻粒度,检测每个时刻有多少个飞机

思路二,扫描线!

不需要检测每一时刻,只需要检测起点或者终点的位置!(交点变化的位置只有起点或者终点)

  1. 将数据拆成二元组 [起点/终点标识,时刻]
  2. 按照时刻排序
  3. 依次扫描
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition of Interval:
* public classs Interval {
* int flag, end;
* Interval(int flag, int end) {
* this.flag = flag;
* this.end = end;
* }
*/
class Point{
int time;
int flag; // 1=start, 0=end
Point(int time, boolean flag){
this.time = time;
this.flag = flag;
}
public static Comparator<Point> pointComparator = new Comparator<Point>(){
public int compare(Point p1, Point p2){
if(p1.time == p2.time) return p1.flag - p2.flag; // 如果时间一致,如果两个都是start或都是end,那么它两相等。如果p1是start而p2是end,那么p1 > p2
else return p1.time - p2.time;
}
}
public int countOfAirplanes(List<Interval> airplanes){
List<Point> list = new ArrayList<>(airplanes.size()*2);
for(Interval i : airplanes){
list.add(new Point(i.start, 1));
list.add(new Point(i.end, 0));
}
Collections.sort(list, Point.PointComparator);
int count = 0, ans = 0;
for(Point p : lists){
// 遇到起点就+1
if(p.flag == 1) ++count;
// 遇到终点就-1
else --count;
ans = Math.max(ans, count);
}
}
}

相关题:meeting rooms。有会议时间安排表。求问多少个会议室能完成这些会议。

2. 扫描线+堆

Building Outline

已知每个楼房的[start, end, height]。例如

1
2
3
4
5
[
[1, 3, 3],
[2, 4, 4],
[5, 6, 1]
]

求楼房的轮廓:

1
2
3
4
5
[
[1, 2, 3],
[2, 4, 4],
[5, 6, 1]
]

思路一,扫描线

一个刻度一个刻度扫描,得到每个刻度下的高度。

思路二,优化扫描线

只需要扫描起点或终点的高度。

例如将上数据变为

1
2
3
4
5
6
[1, T, 3] T代表是开头,F代表结尾
[3, F, 3]
[2, T, 4]
[4, F, 4]
[5, T, 1]
[6, F, 1]

扫描到当前时,需要用到当前的最大值!因此可以引入堆!

在堆上维护当前的最大值,到end时,将这个元素去除。

这个过程可以看https://briangordon.github.io/2014/08/the-skyline-problem.html这里的一个动图

彩色的部分表示堆里的元素,堆里面放的是当前的有效高度

如上图所示,标注的10个点是起点或终点。

  1. 将10个点按照x排序。如果某个点的x坐标一致,那就终点优先。
  2. 依次放入堆中:
    1. 当扫描到1时,1是起点,且堆为空。那么1一定是突变点(从0到有)。点[1, height] 进入候选中心。且点1的高度入堆。
    2. 扫描到2时,2是终点,那么就先把2对应的起点delete掉。此时堆为空,那么2一定是突变点(从有到0),点[2, height = 0] 进入候选中心
    3. 扫描到3时,3是起点,且堆为空。那么3是突变点(从0到3)。点[3,height]进入候选中心。且点3的高度入堆。
    4. 扫描到4时,4是起点,且堆不为空,且4的高度大于当前堆的最大值,那么4是突变点。点[4,height]进入候选中心。且点4的高度入堆。
    5. 扫描到5时,5是起点,且堆不为空,且5的高度大于当前堆的最大值,那么5是突变点。点[5,height]进入候选中心,且点5的高度入堆。
    6. 扫描到6时,6是终点,那么就先把6对应的起点4delete掉。且发现6的高度小于当前堆的最大值,那么6不是突变点。继续
    7. 扫描到7时,7是终点,先把7对应的起点5delete掉。发现7的高度大于当前堆的最大值,那么7是突变点,点[7,height]进入候选中心。
    8. 扫描到8….9….10