扫描线算法
- 扫描线
- 应用
- 应用1：Leetcode.253
- 题目
- 解题思路
- 代码实现
- 类似的题目
- 应用2：Lintcode.821
- 题目
- 解题思路
- 代码实现
- 应用3：Leetcode.218
- 题目
- 解题思路
- 代码实现
- 应用4：Leetcode.850
- 题目
- 解题思路
- 方法一：离散化 + 扫描线
- 方法二：线段树
- 代码实现
- 应用1：Leetcode.253
扫描线
扫描线：假设有一条竖直的直线，从平面的最左端扫描到最右端，在扫描的过程中，直线上的一些线段会被给定的矩形覆盖。如果我们将这些覆盖的线段长度进行积分，就可以得到矩形的面积之和。
如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记：
-
下面的边标记为 \(1\)；
-
上面的边标记为 \(-1\)。
每遇到一个矩形时，我们知道了标记为 \(1\) 的边，我们就加进来这一条矩形的长，等到扫描到 \(-1\) 时，证明这一条边需要删除，那么我们就删除这条边，利用 \(1\) 和 \(-1\) 可以轻松得到这种状态。
还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 \(r+1\) 和 \(r-1\)。
注意，需要 离散化。
应用
应用1：Leetcode.253
题目
253. 会议室 II
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
解题思路
标准扫描线算法，把每个会议的起始时间标记为 \(+1\)，结束时间标记为 \(-1\)，然后将每个时间节点排序，排序时，如果时间相同 \(flag = 1\) 的节点排在 \(flag = -1\) 的节点前面。
然后，依次遍历所有的节点，统计每个节点的最大会议室数目即可。
代码实现
from typing import List
class Node(object):
def __init__(self, _time: int, flag: int):
self.time = _time
self.flag = flag
def __lt__(self, other):
if self.time == other.time:
return self.flag < other.flag
else:
return self.time < other.time
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
nodes = list()
for interval in intervals:
nodes.append(Node(interval[0], 1))
nodes.append(Node(interval[1], -1))
nodes.sort()
count = 0
max_count = 0
for node in nodes:
if node.flag == 1:
count += 1
else:
count -= 1
max_count = max(max_count, count)
return max_count
类似的题目
- 391 · 数飞机
应用2：Lintcode.821
题目
- Time Intersection
Give two users' ordered online time series, and each section records the user's login time point x and offline time point y. Find out the time periods when both users are online at the same time, and output in ascending order.
Example 1:
Input: seqA = [(1,2),(5,100)], seqB = [(1,6)]
Output: [(1,2),(5,6)]
Explanation: In these two time periods (1,2), (5,6), both users are online at the same time.
Example 2:
Input: seqA = [(1,2),(10,15)], seqB = [(3,5),(7,9)]
Output: []
Explanation: There is no time period, both users are online at the same time.
解题思路
扫描线算法，把起点和终点分别记录为\(1\) 和 \(0\)，表示上线 和下线，然后按照 \(time\) 排序。
注意，需要从 \(count = 2\) 时，开始记录起始时刻，\(count\) 从 \(2\) 下降时，则记录结束时刻；
下降的时候，一定要从 \(count = 2\) 的时候开始记录，否则， $1 \to 0 $ 也会被记录进去。
时间复杂度: \((n+m) \times \log_2(n+m)\)
代码实现
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param seqA: the list of intervals
* @param seqB: the list of intervals
* @return: the time periods
*/
private class Node {
public int time;
public int flag;
public Node(int time, int flag) {
this.time = time;
this.flag = flag;
}
}
public List<Interval> timeIntersection(List<Interval> seqA, List<Interval> seqB) {
List<Node> list = new ArrayList<>();
List<Interval> result = new ArrayList<>();
for(Interval interA: seqA) {
list.add(new Node(interA.start, 1));
list.add(new Node(interA.end, -1));
}
for(Interval interB: seqB) {
list.add(new Node(interB.start, 1));
list.add(new Node(interB.end, -1));
}
Collections.sort(list, (a, b) -> (a.time != b.time ? a.time - b.time : a.flag - b.flag));
int count = 0;
int start = -1; int end = -1;
for(Node node: list) {
if(node.flag == 1) {
count++;
if(count == 2) {
start = node.time;
}
}
if(node.flag == -1) {
if(count == 2) {
end = node.time;
result.add(new Interval(start, end));
start = -1;
end = -1;
}
count--;
}
}
return result;
}
}
应用3：Leetcode.218
题目
218. 天际线问题
解题思路
将所有的建筑物边界排序，排序规则如下：
-
x坐标小的在前面；
-
x坐标相同时，高度较大的在前面；
我们维护一个大根堆，用于在扫描线移动过程中，获取每个位置的最大高度。
代码实现
import heapq
from typing import List
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
result = list()
if not buildings:
return result
boundaries = list()
for building in buildings:
boundaries.append((building[0], building[2]))
boundaries.append((building[1], -building[2]))
# 排序规则：x坐标小的在前面，x坐标相同时，高度较大的在前面
boundaries.sort(key=lambda x: (x[0], -x[1]))
pre_height = 0
# 这里我们需要维护一个大根堆，使较大的高度在堆顶
pq = list()
heapq.heappush(pq, 0)
for boundary in boundaries:
# 如果遇到左侧的边界，就将其加入优先级队列
if boundary[1] > 0:
# 大根堆，所以要取高度的负值
heapq.heappush(pq, -boundary[1])
# 如果遇到右侧的边界，就将右侧的边界出队
else:
# 移除该右侧边界
pq.remove(boundary[1])
heapq.heapify(pq)
# 获取堆顶的元素的高度，注意取负值
current = -pq[0]
if current != pre_height:
result.append([boundary[0], current])
pre_height = current
return result
应用4：Leetcode.850
题目
850. 矩形面积 II
给你一个轴对齐的二维数组 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。
计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。返回 总面积 。因为答案可能太大，返回 \(10^9 + 7\) 的 模 。
示例 1：
输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
解释：如图所示，三个矩形覆盖了总面积为 6 的区域。
从(1,1)到(2,2)，绿色矩形和红色矩形重叠。
从(1,0)到(2,3)，三个矩形都重叠。
解题思路
方法一：离散化 + 扫描线
每个矩形都有一个左边界和一个右边界：
-
当扫描到矩形的左边界时，直线上被矩形覆盖的长度可能会增加；
-
当扫描到矩形的右边界时，直线上被矩形覆盖的长度可能会减少。
假设矩形 \(rectangles\) 的个数为 \(n\) ，那么，矩形的左右边界个数为 \(2n\)，因此，扫描线在水平移动过程中，被覆盖的线段长度最多变化 \(2n\) 次，此时，我们就可以将两次变化之间的部分合并起来，一起计算：即这一部分矩形的面积，等于所有被覆盖的线段长度，乘以扫描线在水平方向移动过的距离。
这里会有一个问题，我们如何维护「覆盖的线段长度」呢？
这里同样可以使用到离散化的技巧，扫描线就是一种离散化的技巧，将大范围的连续的坐标转化成 \(2n\) 个离散的坐标。
由于矩形的上下边界也是 \(2n\) 个，它们会将 \(y\) 轴分成 \(2n+1\) 个部分，中间的 \(2n−1\) 个部分均为线段，会被矩形覆盖到，最外侧的 \(2\) 个部分为射线，不会被矩形覆盖到，并且每一个线段要么完全被覆盖，要么完全不被覆盖。
因此我们可以使用一个长度为 \(2n−1\) 的数组 \(coverTimes[i]\)，来表示扫描线上第 \(i\) 个线段被矩形覆盖的次数，即：
-
当扫描线遇到一个左边界时，我们就将左边界覆盖到的所有线段对应的覆盖次数 \(coverTimes[i]\) 全部加 \(1\)；
-
当扫描线遇到一个右边界时，我们就将右边界覆盖到的所有线段对应的覆盖次数 \(coverTimes[i]\) 全部减 \(1\)。
在处理掉一批横坐标相同的左右边界后，\(coverTimes[i]\) 如果大于 \(0\)，说明它被覆盖，我们累加所有被覆盖的线段长度，即可得到「覆盖的线段长度」。
这里，我们使用列表 \(verticalBound\) 保存所有矩形的上下边界，并对其去重，按照从小到大的顺序排序。注意，由于我们对矩形的上下边界排序了，所以，我们需要引入一个变量 \(coverFlag\) 来记录矩形上下边界覆盖的范围。
同时，使用列表 \(sweep\) 记录所有矩形的矩形的左右边界信息：\((x, i, coverFlag)\)，其中，\(x\) 为该矩形边界的横坐标，\(i\) 为该矩形的索引，\(coverFlag\) 为覆盖标记。
对于 \(coverFlag\)：
-
因为扫描线遇到一个矩形的左边界时，扫描线经过的区域会被该矩形覆盖，因此，记录 \(coverFlag = 1\)；
-
因为扫描线遇到一个矩形的右边界时，扫描线经过的区域不会被该矩形覆盖，因此，记录 \(coverFlag = -1\)；
然后，我们对所有 \(sweep\) 记录的左右边界信息，按照横坐标从小到大的顺序排序。
因此，算法的步骤如下：
-
首先，我们按照横坐标从小到大的顺序，遍历所有矩形的左右边界 \(sweep[i]\) ，并跳过所有横坐标相同的左右边界，并记录最后一个相同的左右边界的序号 \(j\)。
-
对于这 \(j - i\) 个具有相同横坐标的左右边界 \(sweep[k]\)：
-
对于任意一个左右边界 \(sweep[k]\)，可以得到：其索引为 \(i =sweep[k][1]\)，覆盖标记为 \(flag=sweep[k][2]\)；
因此，其纵坐标为：\((y1, y2) = (rectangles[i][1], rectangles[i][3])\)。
-
然后，我们需要遍历扫描线上被所有上下边界覆盖的线段；
对于每一条线段 \(L\)：\([verticalBound[p], verticalBound[p + 1]](0 \le p \le 2n - 1)\)，如果它落在 \([y1, y2]\) 范围内，就更新它的覆盖次数 \(coverTimes[p]\)。
-
-
然后，我们需要遍历扫描线上所有被矩形覆盖的线段，并累加覆盖区域的线段长度；
我们可以通过 \(coverTimes[p] \gt 0\)， 判断当前线段是否被矩形覆盖。
-
最后，我们就可以通过通过被覆盖的线段长度和水平扫描过的距离，求出当前的积分区域的面积，并累加该面积的区域
起始扫描的位置为：\(x_0 = sweep[i][0]\)；
水平扫描到的最远距离就是 \(sweep[j + 1]\) 对应的位置，即 \(x_1 = sweep[j + 1][0]\)；
因此，当前积分区域的面积：\(S_i = coveredLength \times (x_1 - x_0) = coveredLength \times (sweep[j + 1][0] - sweep[i][0])\)。
方法二：线段树
方法一中对于数组 \(coverTimes\) 的所有操作，都可以使用线段树进行维护。线段树中需要存储：
-
该节点对应的区间被完整覆盖的次数；
-
该节点对应的区间被覆盖的线段长度。
线段树需要支持：
-
区间增加 1；
-
区间减少 1，并且保证每个被增加 1 的区间在之后一定会减少 1；
-
对于所有非 0 的位置，根据它们的权值进行求和。
由于这种方法严重超纲，因此不在这里详细阐述。
代码实现
【方法一】
from typing import List
class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
# Y轴要扫描的范围
vertical_bound = set()
for rectangle in rectangles:
# 下边界
vertical_bound.add(rectangle[1])
# 上边界
vertical_bound.add(rectangle[3])
vertical_bound = sorted(vertical_bound)
m = len(vertical_bound)
# 记录所有的左右边界
sweep = list()
for i, rectangle in enumerate(rectangles):
# 左边界，遇到覆盖次数加1
sweep.append((rectangle[0], i, 1))
# 右边界，遇到覆盖次数减1
sweep.append((rectangle[2], i, -1))
# 将矩形的所有左右边界按从小到大的顺序排序
sweep.sort()
# cover_times[i] 表示第 i 个线段被矩形覆盖的次数
cover_times = [0] * (m - 1)
result = 0
i = 0
# 遍历所有的X轴的边界
while i < len(sweep):
j = i
# 横坐标相同的左右边界
while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:
j += 1
if j + 1 == len(sweep):
break
# 一次性地处理掉[i, j]范围内，一批横坐标相同的左右边界
for k in range(i, j + 1):
_, index, diff = sweep[k]
# 找到这些边界对应的纵坐标
y1, y2 = rectangles[index][1], rectangles[index][3]
# 遍历扫描线上所有被上下边界覆盖的线段
for p in range(m - 1):
# 如果纵坐标在具有相同X边界的范围内，就更新它的覆盖次数
if y1 <= vertical_bound[p] and vertical_bound[p + 1] <= y2:
cover_times[p] += diff
# 扫描线上被矩形覆盖的线段之和
covered_length = 0
# 遍历扫描线上所有被矩形覆盖的线段
for p in range(m - 1):
if cover_times[p] > 0:
# 纵坐标上每一段覆盖的范围一定是两个相邻线段的差值
covered_length += (vertical_bound[p + 1] - vertical_bound[p])
# 计算扫描线经过范围内被覆盖的面积
result += covered_length * (sweep[j + 1][0] - sweep[i][0])
i = j + 1
return result % (10 ** 9 + 7)
【方法二】
import bisect
from typing import List
class Segtree:
def __init__(self):
self.cover = 0
self.length = 0
self.max_length = 0
@classmethod
def init(cls, tree: List["Segtree"], idx: int, l: int, r: int, hbound: List[int]) -> None:
tree[idx].cover = tree[idx].length = 0
if l == r:
tree[idx].max_length = hbound[l] - hbound[l - 1]
return
mid = (l + r) // 2
cls.init(tree, idx * 2, l, mid, hbound)
cls.init(tree, idx * 2 + 1, mid + 1, r, hbound)
tree[idx].max_length = tree[idx * 2].max_length + tree[idx * 2 + 1].max_length
@classmethod
def update(cls, tree: List["Segtree"], index: int, l: int, r: int, ul: int, ur: int, diff: int) -> None:
if l > ur or r < ul:
return
if ul <= l and r <= ur:
tree[index].cover += diff
cls.pushup(tree, index, l, r)
return
mid = (l + r) // 2
cls.update(tree, index * 2, l, mid, ul, ur, diff)
cls.update(tree, index * 2 + 1, mid + 1, r, ul, ur, diff)
cls.pushup(tree, index, l, r)
@classmethod
def pushup(cls, tree: List["Segtree"], idx: int, l: int, r: int) -> None:
if tree[idx].cover > 0:
tree[idx].length = tree[idx].max_length
elif l == r:
tree[idx].length = 0
else:
tree[idx].length = tree[idx * 2].length + tree[idx * 2 + 1].length
class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
hbound = set()
for rectangle in rectangles:
# 下边界
hbound.add(rectangle[1])
# 上边界
hbound.add(rectangle[3])
hbound = sorted(hbound)
m = len(hbound)
# 线段树有 m-1 个叶子节点，对应着 m-1 个会被完整覆盖的线段，需要开辟 ~4m 大小的空间
tree = [Segtree() for _ in range(m * 4 + 1)]
Segtree.init(tree, 1, 1, m - 1, hbound)
sweep = list()
for i, rectangle in enumerate(rectangles):
# 左边界
sweep.append((rectangle[0], i, 1))
# 右边界
sweep.append((rectangle[2], i, -1))
sweep.sort()
result = 0
i = 0
while i < len(sweep):
j = i
while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:
j += 1
if j + 1 == len(sweep):
break
# 一次性地处理掉一批横坐标相同的左右边界
for k in range(i, j + 1):
_, index, diff = sweep[k]
# 使用二分查找得到完整覆盖的线段的编号范围
left = bisect.bisect_left(hbound, rectangles[index][1]) + 1
right = bisect.bisect_left(hbound, rectangles[index][3])
Segtree.update(tree, 1, 1, m - 1, left, right, diff)
result += tree[1].length * (sweep[j + 1][0] - sweep[j][0])
i = j + 1
return result % (10 ** 9 + 7)
参考：
-
扫描线Sweep Line算法总结
-
Time Intersection
-
线段树
-
矩形面积 II
-
扫描线