非常典型的区间问题。
leetcode第253题,第919题
先直接上高难度的吧,剩下简单的只要根据这个最难的模板套一下,自然就能得到答案。
示例1:
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)
示例二:
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了
贪心的解法:排序(比较器)
先按照会议的开始时间从小到大排序,准备一个小根堆,按照会议的结束时间从小到大排序,如果堆顶的会议结束时间小于等于当前会议的开始时间,说明会议能接上,之前会议开完,当前会议接着开,好比之前一波人开完会后,当前一波人继续用这个会议室开会。此时弹出堆顶的会议,就是利用这个机制保证了不同的会议室。
function minMeetingRooms(intervals: number[][]) {
// 先考虑特殊情况
if (intervals == null || intervals.length == 0) return 0
if (intervals.length == 1) return 1
// 从定义排序按照进入时间排序
intervals.sort((v1, v2) => (v1[0] - v2[0]));
// 定义一个优先队列
let heap = new PriorityQueue()
// 一个计数器
let meetingCount = 0;
for (let meeting of intervals) {
// 要是堆非空,
// 当前会议的开始时间已经大于等于了最小的结束时间
// 这里就是要把所有已经结束的会议淘汰出去
while (!heap.isEmpty() && meeting[0] >= heap.back()) {
heap.dequeue();
}
// 再把当前会议的结束时间加进去
heap.enqueue(meeting[1]); // 堆里有的就是进行的会议的数量
// 更新所需最小会议室数
meetingCount = Math.max(meetingCount, heap.size());
}
return meetingCount;
}
https://leetcode.com/problems/meeting-rooms/
leetcode第252题,第920题。
给定一系列的会议时间间隔,包括起始和结束时间
[[s1,e1],[s2,e2],…],(si < ei)
,确定一个人是否可以参加所有会议。
(0,8),(8,10)
在8这一时刻不冲突
示例1:
输入: intervals = [(0,30),(5,10),(15,20)]
输出: false
解释:
(0,30), (5,10) 和 (0,30),(15,20) 这两对会议会冲突
示例二:
输入: intervals = [(5,8),(9,15)]
输出: true
解释:
这两个时间段不会冲突
贪心:会议按照结束时间从小到大排序,如果后续会议的开始时间小于上次会议的结束时间,直接返回false。或者直接套用上面的模板,如果最小会议室数大于1,自然说明有冲突,so easy。
function minMeetingRooms(intervals: number[][]) {
// 先考虑特殊情况
if (intervals == null || intervals.length == 0) return 0
if (intervals.length == 1) return 1
// 从定义排序按照进入时间排序
intervals.sort((v1, v2) => (v1[0] - v2[0]));
// 定义一个优先队列
let heap = new PriorityQueue()
// 一个计数器
let meetingCount = 0;
for (let meeting of intervals) {
// 要是堆非空,
// 当前会议的开始时间已经大于等于了最小的结束时间
// 这里就是要把所有已经结束的会议淘汰出去
while (!heap.isEmpty() && meeting[0] >= heap.back()) {
heap.dequeue();
}
// 再把当前会议的结束时间加进去
heap.enqueue(meeting[1]); // 堆里有的就是进行的会议的数量
// 谈话不断的看是不是最大的
meetingCount = Math.max(meetingCount, heap.size());
}
return meetingCount;
}
function canAttendMeetings(intervals: number[][]) {
// 先考虑特殊情况
if (intervals == null || intervals.length <= 1) return true
return minMeetingRooms(intervals) > 1;
}
一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间,
你来安排宣讲的日程,要求会议室进行的宣讲的场次最多。
返回最多的宣讲场次。
example:
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
现在只有一个会议室,最多可以安排(5,10),(15,20)两场会议
贪心的核心思路:
所有会议的结束时间从小到大排序,定义会议的结束时间为timeLine
,遍历每个会议,每个会议的开始时间只要大于等于timeLine
,就可以安排,当前的timeLine
来到当前会议的结束时间。
function bestArrange(intervals: number[][]) {
// 先考虑特殊情况
if (intervals == null || intervals.length == 0) return 0
if (intervals.length == 1) return 1
// 从定义排序按照进入时间排序
intervals.sort((v1, v2) => (v1[1] - v2[1]));
let timeLine = 0;
let result = 0;
// 依次遍历每一个会议,结束时间早的会议先遍历
for (let i = 0; i < intervals.length; i++) {
if (timeLine <= intervals[i][0]) {
result++;
timeLine = intervals[i][1];
}
}
return result;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁