leetcode 扫描线专题 06-leetcode.252 meeting room 力扣.252 会议室

news/2024/11/20 23:34:40/

扫描线专题

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

题目

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]] 输出：false 示例 2：

输入：intervals = [[7,10],[2,4]] 输出：true

提示：

0 <= intervals.length <= 10^4

intervals[i].length == 2

0 <= starti < endi <= 10^6

整体思路

一般这种区间的题目，常见的有下面的解决方案：

  1. 暴力

  2. 排序

  3. 扫描线

  4. 优先队列

v1-暴力

思路

直接两层循环，核心是如何判断两个会议室重叠？

重叠条件解释

两个会议的重叠定义为：会议 i 的时间段与会议 j 的时间段有交集。为了检查这种情况，我们考虑以下四种情形：

会议 i 在会议 j 之前结束（没有重叠）：

若 intervals[i][1] <= intervals[j][0]，则会议 i 在会议 j 开始之前结束，说明没有重叠。

会议 i 在会议 j 之后开始（没有重叠）：

若 intervals[j][1] <= intervals[i][0]，则会议 j 在会议 i 开始之前结束，也说明没有重叠。

会议 i 在会议 j 期间发生（有重叠）：

如果 intervals[i][0] < intervals[j][1] 且 intervals[i][1] > intervals[j][0]，则会议 i 的时间段与会议 j 有交集，说明有重叠。

会议 j 在会议 i 期间发生（有重叠）：

如果 intervals[j][0] < intervals[i][1] 且 intervals[j][1] > intervals[i][0]，则会议 j 的时间段与会议 i 有交集，同样说明有重叠。

实现

因为 i,j 是相互的，我们只需要判断一次即可。

java">public static boolean canAttendMeetings(int[][] intervals) {int n = intervals.length;// 双重循环检查每一对会议是否重叠for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 检查会议 intervals[i] 和 intervals[j] 是否重叠if (intervals[i][1] > intervals[j][0] && intervals[j][1] > intervals[i][0]) {return false; // 找到重叠会议，返回 false}}}// 没有重叠会议return true;
}

小结

暴力算法比较容易想到，但是重叠的概念还是需要我们多思考。

v2-排序

思路

我们对数字进行排序。

1) 按照开始时间排序

2）如果当前的开始时间小于上一次的结束时间。则存在重复

现在都开始了，上一次还没有结束。

实现

java">public static boolean canAttendMeetings(int[][] intervals) {int n = intervals.length;Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));// 双重循环检查每一对会议是否重叠for (int i = 1; i < n; i++) {// 本次开始 上一次还没有结束if(intervals[i][0] < intervals[i-1][1]) {return false;}}// 没有重叠会议return true;
}

v3-扫描线算法 sweep line

思路

扫描线算法可以帮助我们处理区间类问题。

我们可以将每个会议的开始时间和结束时间分别标记为 +1 和 -1，然后对所有时间点进行排序并扫描，查看在任一时刻是否有超过一个会议正在进行。

如果有，则表示冲突，无法参加所有会议。

步骤：

  • 将每个会议的开始时间标记为 +1，结束时间标记为 -1，然后合并到一个事件列表 events 中。

  • 按时间顺序对事件进行排序，如果时间相同，则优先处理结束事件（即 -1）。

  • 遍历事件列表，累加标记值，查看任意时刻是否有超过一个会议正在进行。

  • 如果任意时刻会议数量超过 1，则返回 false；否则返回 true。

实现

java">import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class MeetingScheduler {public static boolean canAttendMeetings(int[][] intervals) {List<int[]> events = new ArrayList<>();// 将每个会议的开始和结束时间作为事件存储for (int[] interval : intervals) {events.add(new int[]{interval[0], 1});  // 会议开始时间 +1events.add(new int[]{interval[1], -1}); // 会议结束时间 -1}// 按时间排序，如果时间相同，优先处理结束事件Collections.sort(events, (a, b) -> (a[0] == b[0]) ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));int ongoingMeetings = 0;// 扫描事件列表，检查会议的重叠情况for (int[] event : events) {ongoingMeetings += event[1];  // 加上当前事件的标记值if (ongoingMeetings > 1) {return false; // 有重叠会议}}return true; // 没有重叠会议}
}

为什么要这样排序？

在扫描线算法中，我们对事件的排序方式有特定的规则，这样排序是为了正确处理时间相同的开始和结束事件，避免错误的计数。

排序规则解释

在扫描线问题中，我们通常将每个区间拆分为两个事件，一个开始事件和一个结束事件。我们按照以下规则对所有事件进行排序：

  1. 按时间（a[0]）升序排列：这保证了我们按时间顺序扫描所有事件。
  2. 时间相同时，优先处理结束事件（即 a[1] 进行二次排序）：如果两个事件的时间相同，我们通过让结束事件优先于开始事件来避免计数错误。

为什么时间相同时优先处理结束事件？

在扫描线算法中，优先处理结束事件可以避免错误的重叠判断。

例如：

  • 如果两个会议的结束时间和下一个会议的开始时间相同，那么优先处理结束事件可以让我们在下一个会议开始前，结束当前会议，确保不会被错误地计为重叠。

  • 如果我们不优先处理结束事件，在计数上可能会把开始事件算在前一个活动上，从而导致错误的结果（如错误地增加了计数）。

具体排序语句解释

以下代码是具体的排序语句：

java">Collections.sort(events, (a, b) -> (a[0] == b[0]) ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
  • a[0] == b[0]：首先比较事件发生的时间。如果两个事件的时间相同，则 a[1] 和 b[1] 的比较决定优先级。
  • Integer.compare(a[1], b[1])：时间相同的情况下，a[1] 和 b[1] 的值决定排序。通常，我们用 +1 表示开始事件，-1 表示结束事件，因此结束事件优先级高（-1 小于 +1）。
  • Integer.compare(a[0], b[0])：时间不同的情况下，按照事件的时间排序（从小到大）。

示例说明

假设有三个会议时间：[5, 10], [5, 12], [10, 15]。拆解事件后：

[(5, +1), (10, -1), (5, +1), (12, -1), (10, +1), (15, -1)]

排序结果为：

[(5, +1), (5, +1), (10, -1), (10, +1), (12, -1), (15, -1)]

综上所述

按这种顺序排序，可以确保时间相同的情况下优先结束事件，从而正确地处理重叠区间并维护扫描线的计数。

小结

看起来这个扫描线算法还是比较有趣的，后面我们专门一个系列学习一下。

v4-使用优先队列（最小堆）

思路

这种方法通过维护一个最小堆来跟踪当前正在进行的会议，适合在更复杂的情况下进一步扩展。

例如，计算一个人最多能同时参加的会议数目等。

步骤：

  1. 按开始时间排序 intervals。
  2. 使用最小堆（优先队列）来保存当前正在进行的会议结束时间。
  3. 对于每个会议，检查堆顶的结束时间（即最早结束的会议）是否小于等于当前会议的开始时间：
    • 如果是，则说明前一个会议已结束，可以移除堆顶。
    • 否则，将当前会议的结束时间加入到堆中。
  4. 如果堆中有多个会议的结束时间存在，则表示冲突，返回 false；否则返回 true。

实现

java">import java.util.Arrays;
import java.util.PriorityQueue;public class MeetingScheduler {public static boolean canAttendMeetings(int[][] intervals) {// 按开始时间排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));// 最小堆用于跟踪会议的结束时间PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int[] interval : intervals) {// 如果堆顶的会议结束时间小于等于当前会议的开始时间，弹出堆顶if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {minHeap.poll();}// 将当前会议的结束时间加入堆中minHeap.add(interval[1]);// 如果堆中有超过一个会议的结束时间，说明有重叠if (minHeap.size() > 1) {return false;}}return true;}
}

为啥要用优先级队列？

优先级队列（PriorityQueue）在扫描线算法中的作用主要是动态地管理和维护当前活动的区间或事件。

即使我们先对所有事件进行了排序，使用优先级队列在扫描过程中仍然可以有效地处理区间重叠、活动计数等问题。

为什么排序之后不直接对比而要用优先级队列？

虽然排序能够帮助我们按时间顺序处理事件，但在扫描过程中，动态维护当前活动的区间或事件是很重要的。

这就是优先级队列的作用。它可以在扫描过程中高效地维护哪些区间或事件仍然处于“活跃”状态。

优先级队列的关键作用

  1. 动态更新活动状态：

    • 在扫描过程中，我们需要保持一个活跃的集合，即哪些区间正在被处理（比如会议正在进行中）。这些区间的状态会随着时间推移而变化。

    • 优先级队列可以让我们在每个事件发生时快速地进行添加、删除和更新操作。例如，当会议开始时，我们将其添加到优先级队列中；当会议结束时，我们将其从队列中移除。

  2. 高效获取当前活动状态：

    • 在扫描过程中，每当遇到一个事件时，我们需要判断当前活动的区间或事件是否满足特定条件（例如当前同时进行的会议数量，或者判断是否有重叠的区间）。使用优先级队列可以让我们在 O(log n) 时间内快速地插入和删除事件，并且始终能够访问当前最优的区间或状态。

  3. 保持区间顺序：

    • 虽然我们已经对所有事件进行了排序，但在扫描过程中，活动区间的结束时间是动态变化的。因此，使用优先级队列可以帮助我们动态地维护一个按结束时间排序的集合。这样每次我们需要知道最早结束的区间时，可以在 O(1) 时间内获取。

典型的使用场景

以经典的 会议室问题（LC 253）为例：

1. 事件排序：

我们首先将所有的开始事件和结束事件按照时间进行排序。如果时间相同，我们优先处理结束事件。排序后的事件列表可能如下：

   [(5, +1), (5, +1), (10, -1), (10, +1), (12, -1), (15, -1)]
2. 使用优先级队列维护活动会议：

在扫描事件时，我们需要维护当前活跃的会议。例如，我们可能希望知道目前有多少会议在同时进行。每当遇到一个开始事件（+1），我们将其加入优先级队列；每当遇到一个结束事件（-1），我们将其从优先级队列中移除。

使用优先级队列可以确保：

  • 对于每个会议，按开始时间和结束时间进行正确排序。
  • 在遇到结束事件时，能够及时从队列中移除已经结束的会议。
3. 最小会议室数：

每次扫描到一个开始事件时，我们会将当前活动的会议数增加；每次扫描到结束事件时，我们会减少当前活动的会议数。我们通过维护当前活动会议的数量，最终可以得到最大并发的会议数，也就是所需的最小会议室数。

这时，优先级队列的作用是：

  • 插入操作：在遇到一个开始事件时，向队列中插入新的会议。
  • 删除操作：在遇到一个结束事件时，从队列中删除结束的会议。
4. 具体实现细节：

假设我们使用一个优先级队列来保存当前正在进行的会议的结束时间。每当遇到开始事件时，我们将该会议的结束时间加入队列；每当遇到结束事件时，我们将其从队列中移除。

优先级队列在这里的作用：

  1. 维护活动会议：优先级队列根据结束时间维护当前正在进行的会议的结束时间。在扫描事件时，能够高效地添加、删除结束的会议。

  2. 统计活动会议数：在扫描过程中，队列的大小代表当前正在进行的会议数，最终输出的最大队列大小即为所需的最小会议室数。

总结

排序后的事件只是帮助我们按时间顺序扫描事件。

优先级队列则通过动态管理活跃区间（如会议的结束时间等），保证我们能高效地判断每个时刻的活动状态，快速获得当前活跃区间的数量或其它信息。

在这种问题中，排序加优先级队列的组合为扫描线算法提供了高效且灵活的解决方案。

小结

不得不说，用数组替代 map 的方法确实令人叹为观止。

那么，我们前面的 two-sum 是不是也可以这样优化？

开源地址

为了便于大家学习，所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode


http://www.ppmy.cn/news/1548602.html

相关文章

利用python 检测当前目录下的所有PDF 并转化为png 格式

利用python 检测当前目录下的所有PDF 并转化为png 格式

以下是一个完整的 Python 脚本&#xff0c;用于检测当前目录下的所有 PDF 文件并将每一页转换为 PNG 格式&#xff1a; import os from pdf2image import convert_from_path# 设置输出图像的 DPI&#xff08;分辨率&#xff09; DPI 300# 获取当前目录 current_directory os…
阅读更多...
通过css的哪些方式可以实现隐藏页面上的元素？

通过css的哪些方式可以实现隐藏页面上的元素？

1&#xff1a;opacity:0 通过将元素的透明度设置为o&#xff0c;实现隐藏效果&#xff0c;但是依然会占用空间并可以进行交互。 2&#xff1a;visibility:hidden 与透明度度为0的方案类似&#xff0c;会占据空间&#xff0c;但不可以进行交互。 3&#xff1a;Overflow:hi…
阅读更多...
k8s服务内容滚动升级以及常用命令介绍

k8s服务内容滚动升级以及常用命令介绍

查看K8S集群所有的节点信息 kubectl get nodes 删除K8S集群中某个特定节点 kubectl delete nodes/10.0.0.123 获取K8S集群命名空间 kubectl get namespace 获取K8S所有命名空间的那些部署 kubectl get deployment --all-namespaces 创建命名空间 web界面上看到的效果,但是…
阅读更多...
计算机网络学习笔记-3.3以太网和局域网

计算机网络学习笔记-3.3以太网和局域网

以太网 以太网&#xff08;Ethernet&#xff09;是一种用于计算机网络的技术规范&#xff0c;广泛应用于局域网&#xff08;LAN&#xff09;的构建。它定义了如何在网络设备之间传输数据&#xff0c;并确保这些数据能够被可靠传送。以太网是目前最常见和最广泛使用的局域网技术…
阅读更多...
【Anomaly Detection论文阅读记录】PaDiM与PatchCore模型的区别与联系

【Anomaly Detection论文阅读记录】PaDiM与PatchCore模型的区别与联系

PaDiM与PatchCore模型的区别与联系 背景介绍 PADIM（Pretrained Anomaly Detection via Image Matching）和 PatchCore 都是基于深度学习的异常检测方法，主要用于图像异常检测，尤其是在无监督学习设置下。 PADIM 是一种通过利用预训练的视觉模型（例如，ImageNet预训练的卷…
阅读更多...
Python绘制雪花

Python绘制雪花

文章目录 系列目录写在前面技术需求完整代码代码分析1. 代码初始化部分分析2. 雪花绘制核心逻辑分析3. 窗口保持部分分析4. 美学与几何特点总结 写在后面 系列目录 序号直达链接爱心系列1Python制作一个无法拒绝的表白界面2Python满屏飘字表白代码3Python无限弹窗满屏表白代码4…
阅读更多...
Hadoop 学习心得

Hadoop 学习心得

一、引言 &#xff08;一&#xff09;学习 Hadoop 的背景和目的 随着信息技术的飞速发展&#xff0c;数据量呈爆炸式增长&#xff0c;传统的数据处理方式已难以满足需求。在这样的背景下&#xff0c;为了能够在大数据领域有所发展&#xff0c;我开始学习 Hadoop。Hadoop 作为处…
阅读更多...
【会话文本nlp】对话文本解析库pyconverse使用教程版本报错、模型下载等问题解决超参数调试

【会话文本nlp】对话文本解析库pyconverse使用教程版本报错、模型下载等问题解决超参数调试

前言&#xff1a; 此篇博客用于记录调用pyconverse库解析对话文本时遇到的问题与解决思路&#xff0c;以供大家参考。 文章目录 pycoverse介绍代码github链接问题解决1 [cannot import name ‘cached_download‘ from ‘huggingface_hub‘ 问题解决](https://blog.csdn.net/wei…
阅读更多...
最新文章

Copyright @ 2022~2023