
mzoe666888
V1
2022/04/20阅读:58主题:兰青
内卷大厂系列《会议室问题三连击》
大厂高频算法面试题:《会议室问题系列》,您将学到如何利用贪心算法来解决问题,贪心的思想就是人类自然智慧的体现,往好的利益出发,贪心的题目一般利用比较器、堆来解题。
一、会议室问题 I
给定一系列的会议时间间隔,包括起始和结束时间
[[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
解释:
这两个时间段不会冲突
1、分析
贪心:利用人类的自然智慧来解题,会议按照结束时间从小到大排序,如果后续会议的开始时间小于上次会议的结束时间,直接返回false。
2、实现
public class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
// 贪心:利用人类的自然智慧
public boolean canAttendMeetings(List<Interval> intervals) {
if(intervals == null || intervals.size() < 2) {
return true;
}
// 会议按照结束时间从小到大排序
Collections.sort(intervals, Comparator.comparingInt(o -> o.end));
int timeLine = intervals.get(0).end; // 第一个会议室的结束时间
for(int i = 1; i < intervals.size(); i++) {
Interval meet = intervals.get(i);
int start = meet.start;
if(start < timeLine) { // 如果后续会议的开始时间小于上次会议的结束时间,直接返回false
return false;
}else { // 更新会议的结束时间
timeLine = meet.end;
}
}
return true;
}
二、会议室问题 II
一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间,
你来安排宣讲的日程,要求会议室进行的宣讲的场次最多。
返回最多的宣讲场次。
1、分析
贪心的核心思路:
所有会议的结束时间从小到大排序,定义会议的结束时间为timeLine,遍历每个会议,每个会议的开始时间只要大于等于timeLine,就可以安排,当前的timeLine来到当前会议的结束时间。
2、实现
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
// 贪心
// 会议的开始时间和结束时间,都是数值,不会 < 0
public static int bestArrange(Program[] programs) {
Arrays.sort(programs, new ProgramComparator());
int timeLine = 0;
int result = 0;
// 依次遍历每一个会议,结束时间早的会议先遍历
for (int i = 0; i < programs.length; i++) {
if (timeLine <= programs[i].start) {
result++;
timeLine = programs[i].end;
}
}
return result;
}
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
三、会议室问题 III
给定一系列的会议时间间隔intervals,包括起始和结束时间
[[s1,e1],[s2,e2],...] (si < ei)
,找到所需的最小的会议室数量。
示例1:
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)
示例二:
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了
1、分析
贪心:按照人类的自然智慧分析题目即可。
贪心的解法:排序(比较器)
先按照会议的开始时间从小到大排序,准备一个小根堆,按照会议的结束时间从小到大排序,如果堆顶的会议结束时间小于等于当前会议的开始时间,说明会议能接上,之前会议开完,当前会议接着开,好比之前一波人开完会后,当前一波人继续用这个会议室开会。此时弹出堆顶的会议,就是利用这个机制保证了不同的会议室。
2、实现
// 贪心:按照人类自然智慧分析
public int minMeetingRooms(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0) {
return 0;
}
if (intervals.size() == 1) {
return 1;
}
// 会议按照开始时间从小到大排序
Collections.sort(intervals, Comparator.comparingInt(o -> o.start));
// 准备一个小根堆,按照会议结束时间从小到大排序
PriorityQueue<Interval> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.end));
int max = 0;
for (Interval meet : intervals) {
// 之前会议的结束时间小于等于当前会议的开始时间,说明会议能连接起来,把之前的会议弹出
while (!heap.isEmpty() && heap.peek().end <= meet.start) {
heap.poll();
}
heap.add(meet);
// 堆中会议的大小就是能安排的会议数量
max = Math.max(max, heap.size());
}
return max;
}
作者介绍

mzoe666888
V1