leetcode 数组专题 06-扫描线算法(Sweep Line Algorithm)

ops/2024/11/20 0:29:52/

扫描线专题

leetcode 数组专题 06-扫描线算法(Sweep Line Algorithm)

leetcode 数组专题 06-leetcode.218 the-skyline-problem 力扣.218 天际线问题

leetcode 数组专题 06-leetcode.252 meeting room 力扣.252 会议室

leetcode 数组专题 06-leetcode.253 meeting room ii 力扣.253 会议室 II

什么是扫描线算法?

扫描线算法(Sweep Line Algorithm)是一种常用于解决几何问题(尤其是涉及区间、时间线或事件的重叠问题)的算法。

它的基本思想是“模拟一条扫描线从一个方向扫过所有事件”,在扫描过程中维护一个数据结构来追踪当前的状态(例如活动区间的数量、最小值、最大值等)。

扫描线算法的基本步骤

  1. 事件表示:每个问题中的区间(例如会议时间)或事件,都可以转化为若干个关键事件(例如开始时间和结束时间)。

  2. 事件排序:将所有事件按照时间排序(如果时间相同,则根据事件的类型来排序,例如结束事件优先于开始事件)。

  3. 扫描过程:从最早的事件开始,按照排序顺序逐一处理每个事件,并在处理每个事件时更新状态(例如活动会议的数量、最大活动时间等)。

  4. 数据维护:根据事件类型,更新当前的活动状态。例如,遇到一个开始事件时,我们增加一个计数,遇到结束事件时,减少计数,或者更新其他需要维护的值。

  5. 输出结果:在扫描过程中,根据需求输出解答。

应用场景

扫描线算法广泛应用于处理各种区间问题,典型的应用包括:

  • 会议安排(检测会议时间是否有重叠)
  • 区间覆盖问题(检查是否有足够的资源覆盖所有区间)
  • 计算最大并发数(计算在某一时间点活跃的事件数量,如计算最多同时存在的会议数)
  • 凸包问题(计算一个点集的最小凸包)

扫描线算法的具体步骤

1. 事件表示与排序

假设我们有若干个区间(如会议的开始时间和结束时间),我们首先将每个区间拆解为两个事件:

一个是开始事件,另一个是结束事件。

每个事件可以表示为一个元组 (time, type),其中 time 表示事件发生的时间,type 可以是 +1(表示开始)或者 -1(表示结束)。

例如,会议区间 [(5, 10), (8, 12), (13, 16)] 可以拆解为事件:

[(5, +1), (10, -1), (8, +1), (12, -1), (13, +1), (16, -1)]

事件按时间排序。如果有多个事件发生在相同的时间点,则优先处理结束事件,因为结束事件可以使得下一个开始事件得以处理。

2. 事件扫描与状态更新

扫描线的核心是对事件的处理。在扫描线遍历时,我们保持一个计数器(或其他数据结构)来跟踪当前的活动状态。对于会议安排问题,我们使用一个计数器来记录当前同时进行的会议数量。

  • 当遇到一个 开始事件+1),增加计数器,表示新的会议开始。
  • 当遇到一个 结束事件-1),减少计数器,表示一个会议结束。
3. 结果输出

在扫描过程中,我们可以输出每个时间点的活动状态。例如,我们可以在每次更新计数器时,检查当前同时进行的会议数,或者记录最大会议数等。

例子:检测会议是否有重叠

假设我们有一组会议的时间区间,使用扫描线算法来判断是否所有会议都能参加。

给定的会议区间:[[0, 30], [5, 10], [15, 20]]

1. 拆解事件

我们将每个会议区间拆解成开始事件和结束事件:

[(0, +1), (30, -1), (5, +1), (10, -1), (15, +1), (20, -1)]
2. 事件排序

按时间排序事件,时间相同的情况下优先处理结束事件:

[(0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1)]
3. 扫描事件并更新状态

我们从第一个事件开始,逐一扫描:

  • 在时间 0 处,遇到开始事件 +1,活动会议数增加到 1。
  • 在时间 5 处,遇到开始事件 +1,活动会议数增加到 2,说明此时有两个会议重叠。
  • 在时间 10 处,遇到结束事件 -1,活动会议数减少到 1。
  • 在时间 15 处,遇到开始事件 +1,活动会议数增加到 2,说明此时又有两个会议重叠。
  • 在时间 20 处,遇到结束事件 -1,活动会议数减少到 1。
  • 在时间 30 处,遇到结束事件 -1,活动会议数减少到 0。
4. 判断是否有重叠

在扫描过程中,我们发现活动会议数有过大于 1 的情况(特别是在时间 5 和时间 15),因此有重叠会议,返回 false

扫描线算法的优势

  1. 时间复杂度:事件排序的时间复杂度是 O(n log n),其中 n 是会议数或事件数。扫描线的遍历时间复杂度是 O(n)。因此,整体时间复杂度是 O(n log n),比暴力算法(O(n^2))要高效得多。

  2. 空间复杂度:需要存储所有事件,空间复杂度为 O(n)

  3. 易于扩展:扫描线算法可以很容易地适应更多的需求,例如统计某一时刻活动的最大数量、求得活动的区间并进行其他计算等。

扩展应用

  • 最大并发活动数:通过扫描线算法,我们可以轻松地计算在某个时刻同时进行的最多会议数(即最大并发数)。
  • 区间合并:我们还可以通过扫描线算法来合并重叠的区间。
  • 区间覆盖:检查一组区间是否能完全覆盖一个目标区间等。

总结

扫描线算法是一种非常强大且高效的算法,尤其适用于处理与区间重叠、事件排序相关的几何问题。

在许多情况下,它比暴力算法要高效得多,尤其是在数据量大的时候,能够显著减少计算的复杂度。

参考资料

https://leetcode.cn/problems/4sum/


http://www.ppmy.cn/ops/135103.html

相关文章

奇文网盘部署指南

内容来自官方 官方地址 https://pan.qiwenshare.com/docs/guide/install.html#%E5%90%8E%E5%8F%B0 #下载编译 #后台 git clone https://gitee.com/qiwen-cloud/qiwen-file.git本项目是本质上是一个maven工程,因此,在命令行执行普通的maven编译命令即可…

.netcore + postgis 保存地图围栏数据

一、数据库字段 字段类型选择(Type) 设置对象类型为:geometry 二、前端传递的Json格式转换 前端传递围栏的各个坐标点数据如下: {"AreaRange": [{"lat": 30.123456,"lng": 120.123456},{"lat": 30.123456…

Javaweb梳理16——HTMLCSS使用

Javaweb梳理16——HTML&CSS使用 16 快速入门16.1 基础标签16.2 图片、音频、视频标签16.3 超链接标签16.4 列表标签16.5 表格标签16.6 布局标签16.7 表单标签16.8 type取值 16 快速入门 1.新建文本文件&#xff0c;后缀名改为 .html/.htm 2.编写 HTML结构标签 3.在<bod…

关于Java合并多个Excel中的数据【该数据不是常规列表】,并入库保存的方案

1. 背景 最近在使用RPA&#xff08;机器人流程自动化&#xff09;做数据采集的时候。发现那个RPA采集&#xff0c;一次只能采集相同格式的数据&#xff0c;然后入到Excel或者库中。由于院内系统的业务限制&#xff0c;导致采集的数据是多个Excel&#xff0c;并且我们这边的需求…

Android Framework AMS(16)进程管理

该系列文章总纲链接&#xff1a;专题总纲目录 Android Framework 总纲 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节主要解读AMS 进程方面的知识。关注思维导图中左上侧部分即可。 我们本章节主要是对Android进程管理相关知识有一个基本的了解。先来了解下L…

Pr:音频过渡

Adobe Premiere Pro 自带一组共三个音频过渡 Audio Transitions效果。 对音频剪辑之间应用交叉淡化 Crossfade过渡&#xff0c;操作方式类似于应用视频过渡效果。 对于交叉淡化&#xff0c;要保证前剪辑的出点之后及后剪辑的入点之前有足够的预留内容&#xff08;也称“手柄”&…

【HarmonyOS】Hdc server port XXXX has been used.Configure environment variable

【HarmonyOS】Hdc server port XXXX has been used.Configure environment variable 一、 问题背景&#xff1a; 无法调试debug应用&#xff0c;IDE右下角显示该弹窗&#xff1a; Hdc server port XXXX has been used.Configure environment variable ‘OHOS_HDC_SERVER_POR…

Typora2024最新版破解方法(亲测可用)

此方法非常简单&#xff0c;无需安装dll补丁&#xff0c;无需修改注册表&#xff0c;无需使用老版本。仅需修改部分文件内容即可 方法步骤 步骤一 下载并安装Typora 安装Typora 打开官网 下载并安装最新版即可 点击访问Typora官网 https://typoraio.cn/ 步骤二 修改文件 …