253. 会议室 II
难度中等317收藏分享切换为英文接收动态反馈
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
示例 1：
输入：intervals = [[0,30],[5,10],[15,20]] 输出：2
示例 2：
输入：intervals = [[7,10],[2,4]] 输出：1
提示：
- 1 <= intervals.length <= 104
- 0 <= starti < endi <= 106
思路一：模拟
1、记录开始时间和结束时间对应的会议序列，
set 记录相同开始时间下，不同的结束时间列表
outs记录相同结束时间下，不同的开始时间列表
2、遍历所有时间点
- list 存放正在运行的任务，
- room 记录当前会议室的用量
- 若当前时间是开始时间点，则用结束时间列表的长度来更新room变量。
- 若当前时间是结束时间点，则以当前时间点来过滤list列表，记录list列表前后的变化量，并更新到room变量
3、每个迭代，更新结果ans。
/*** @param {number[][]} intervals* @return {number}*/var minMeetingRooms = function(intervals) {const set = new Map(), outs = new Map(), times = new Set();for (let [s, e] of intervals) {times.add(s).add(e);if (!set.has(s)) {set.set(s, []);}set.get(s).push(e);if (!outs.has(e)) {outs.set(e, []);}outs.get(e).push(s);}let ans = 0, room = 0, list = [];const ps = [...times.keys()].sort((a, b) => a-b);// console.log(ps);for (let p of ps) {// console.log(p, room, ans, list);if (set.has(p)) { // startconst outs = set.get(p);if (outs.length) {room += outs.length;outs.forEach((e) => list.push([p, e]));}}if (outs.has(p)){let oldLen = list.length;list = list.filter(([s, e]) => e > p);room -= (oldLen - list.length);}ans = Math.max(room, ans);}return ans;};
思路一：模拟 + 小空间优化：outs只记录结束时间，不记录开始时间，所以可以改用Set 来记录。
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
const set = new Map(), outs = new Set(), times = new Set();
for (let [s, e] of intervals) {
times.add(s).add(e);
if (!set.has(s)) {
set.set(s, []);
}
set.get(s).push(e);
outs.add(e);
}
let ans = 0, room = 0, list = [];
const ps = [...times.keys()].sort((a, b) => a-b);
// console.log(ps);
for (let p of ps) {
// console.log(p, room, ans, list);
if (set.has(p)) { // start
const outs = set.get(p);
if (outs.length) {
room += outs.length;
outs.forEach((e) => list.push([p, e]));
}
}
if (outs.has(p)){
let oldLen = list.length;
list = list.filter(([s, e]) => e > p);
room -= (oldLen - list.length);
}
ans = Math.max(room, ans);
}
return ans;
};
思路一：模拟，set和outs的空间优化，
1、 观察上面的代码，发现，sets,和outs的values 并没有完全使用，后面只用到了values的长度，所以在前面构造数据的时候，直接计数；
2、times这个集合多余，也可以去除
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
const set = new Map(), outs = new Map();
for (let [s, e] of intervals) {
if (!set.has(s)) {
set.set(s, 1);
} else {
set.set(s, set.get(s) + 1);
}
if (!outs.has(e)) {
outs.set(e, 1);
} else {
outs.set(e, outs.get(e) + 1);
}
}
let ans = 0, room = 0;
const ps = [...set.keys(), ...outs.keys()].sort((a, b) => a-b);
for (let p of ps) {
if (set.has(p)) { // start
room += set.get(p);
}
if (outs.has(p)){
let oldLen = outs.get(p);
room -= oldLen;
}
ans = Math.max(room, ans);
}
return ans;
};
// 代码变形版本，便于观察，找规律，下一个版本将基于这个变形版本做优化。
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
const ins = new Map(), outs = new Map(), times = new Set();
for (let [s, e] of intervals) {
times.add(s).add(e);
ins.set(s, ins.has(s) ? (ins.get(s) + 1) : 1);
outs.set(e, outs.has(e) ? (outs.get(e) + 1) : 1);
}
let ans = 0, room = 0;
const ps = [...times.keys()].sort((a, b) => a-b);
for (let p of ps) {
room += ins.has(p) ? ins.get(p) : 0;
room -= outs.has(p) ? outs.get(p) : 0;
ans = Math.max(room, ans);
}
return ans;
};
思路二：模拟 + 增量计算
考虑上面版本的第二个变形写法，发现在模拟的循环中开始时加法运算，结束时剑法运算，考虑一个思路，将这个加加减减的增量提前到前半部分的时间点数据准备阶段完成，则可以在开始时间点的时候，+1计数，结束时间点的时候-1计数，这样两个时间点集合可以合并为一个times。最后代码如下。
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
const times = new Map();
for (let [s, e] of intervals) {
times.set(s, times.has(s) ? (times.get(s) + 1) : 1);
times.set(e, times.has(e) ? (times.get(e) - 1) : -1);
}
let ans = 0, room = 0;
const ps = [...times.keys()].sort((a, b) => a-b);
for (let p of ps) {
room += times.has(p) ? times.get(p) : 0;
ans = Math.max(room, ans);
}
return ans;
};
思路三：插旗法
考虑思路二的增量计算过程，发现times这个map似乎没有太强的必要性，决定结果大小的不是times这个容器的选择，而是数据计算顺序的选择，可以考虑将增量数据与存储方式剥离，简化代码逻辑。
时间序列和计数存储：选择简单的数组存储，每个会议存储[s,1],[e,-1], s和e分表代表第i会议的开始和结束时间，用变量times表示存储后的数组容器。
这样times数组中每个元素的第一个为时间点，第二个为该时间点的增量。
计算顺序：对times变量进行排序，由于要满足所有会议，所以贪心选择以开始时间非降序排序，如果开始时间相同，则以增量（结束时间，这里就两种值，-1和1，-1代表结束时间，1代表开始时间）的非降序排序，一句话，先开始先结束的优先安排会议室。
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
const times = [];
for (let [s, e] of intervals) {
times.push([e, -1]);
times.push([s, 1]);
}
const ps = times.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
let ans = 0, room = 0;
for (let [t, v] of ps) {
room += v;
ans = Math.max(room, ans);
}
return ans;
};
435. 无重叠区间
思路一：排序结束时间，从前向后遍历，计数不重叠区间。
/**
* @param {number[][]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function(intervals) {
intervals.sort((a, b) => a[1] - b[1]);
let min = Number.NEGATIVE_INFINITY, ans = 0;
for (let i = 0; i < intervals.length; i++) {
if (intervals[i][0] >= min) {
ans ++;
min = intervals[i][1];
}
}
return intervals.length - ans;
};
思路二：排序开始时间，从后向前遍历，计数不重叠区间
/**
* @param {number[][]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let limit = Number.POSITIVE_INFINITY, ans = 0;
for (let i = intervals.length - 1; i >= 0; i--) {
if (intervals[i][1] <= limit) {
ans ++;
limit = intervals[i][0];
}
}
return intervals.length - ans;
};
452. 用最少数量的箭引爆气球
思路一：以结束时间排序，计数不重叠的区间，从前向后遍历，判断每个区间的开始时间大于前一个的结束时间
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
points.sort((a, b) => a[1] - b[1]);
let min = Number.MIN_SAFE_INTEGER;
let ans = 0;
for (let i = 0; i < points.length; i++) {
if (points[i][0] > min) {
ans += 1;
min = points[i][1];
}
}
return ans;
};
思路二：以开始时间排序，计数不重叠的区间，从后向前遍历，判断每个区间的结束时间小于后一个的开始时间
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
points.sort((a, b) => a[0] - b[0]);
let max = Number.MAX_SAFE_INTEGER;
let ans = 0;
for (let i = points.length - 1; i >= 0; i--) {
if (points[i][1] < max) {
ans += 1;
max = points[i][0];
}
}
return ans;
};
1353. 最多可以参加的会议数目
/**
* @param {number[][]} events
* @return {number}
*/
var maxEvents = function(events) {
const pq = new MinPriorityQueue();
let max = events[0][1];
events.sort((a, b) => {
max = Math.max(max, a[1], b[1]);
return a[0] - b[0];
});
const push = (e) => pq.enqueue(e);
const pop = () => pq.dequeue();
const peek = () => pq.front().element;
const isEmpty = () => pq.isEmpty();
let i = 0, res = 0, n = events.length;
for (let d = 1; d <= max; d += 1) {
// 弹出已经结束的会议
while (!isEmpty() && peek() < d) {
pop();
}
// 将开始时间为d的会议都入队列， 以结束时间最小堆为高优先级
while (i < n && events[i][0] === d) {
push(events[i][1]);
i += 1;
}
// 弹出第d天可以选择的会议。
if (!isEmpty()) {
pop();
res += 1;
}
}
return res;
};
若有收获，就点个赞吧
0 人点赞
