练习扫描线算法
视频:基础算法(一) -- 扫描线_哔哩哔哩_bilibili
391 · Number of Airplanes in the Sky - LintCode 【基础】
“这个是扫描线的基础题,后面其他题目都是它的套娃。”
253. 会议室 II - 力扣(LeetCode)【MID】
思路1:扫描线算法,很简单。复杂度分析:O(nlogn),空间: O(n) 【实现非常简单,固定套路】
class Solution {
public int minMeetingRooms(int[][] A) {
// swipping line
List<int[]> points = new ArrayList<>();
for(int[] a : A) {
points.add(new int[] {a[0], 1});
points.add(new int[] {a[1], -1}); // 这里设置-1,方便后续遍历时,直接累加。而不需要判断是开始还是结束
}
Collections.sort(points, (x, y) -> {
if (x[0] != y[0]) return Integer.compare(x[0], y[0]);
return Integer.compare(x[1], y[1]);
});
int ans = 0, count = 0;
for (int[] point : points) {
count += point[1];
ans = Math.max(ans, count);
}
return ans;
}
}
思路2:优先队列。复杂度分析:O(nlogn)
class Solution {
public int minMeetingRooms(int[][] A) { // 优先队列
int n = A.length;
// 对会议按开始时间排序,我们先安排最先开始的会议
Arrays.sort(A, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
// 记录每个会议室的结束时间
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 对于第一个会议,肯定要分配一间会议室
pq.offer(A[0][1]);
for(int i = 1; i < n; i++) {
// 至于当前的会议A[i] 我需要看,目前分配的会议室是否够用,有没有哪一个已经结束了
if (A[i][0] >= pq.peek()) { // 可以共用堆顶的这个会议室
pq.poll();
}
pq.offer(A[i][1]);
}
// 队列中记录了分配的每个会议室,最后一场会议的结束时间
return pq.size();
}
}
标签:02,pq,06,会议室,int,points,扫描线,2023,return
From: https://www.cnblogs.com/xianzhon/p/17453016.html