1.会议室（252-easy）
题目描述：给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议，即判断是否存在重叠区域！
示例：
输入: intervals = [[0,30],[5,10],[15,20]]
输出: false
解释: 存在重叠区间，一个人在同一时刻只能参加一个会议。
思路：对每个会议时间按照开始时间排序（关键）。然后遍历数组进行判断，如果前一个会议结束的时间大于后一个会议开始的时间（前一个还没结束，后一个就开始了），则存在重叠区域。
代码：
public boolean canAttendMeetings(int[][] intervals) {
if (intervals == null || intervals.length == 0) return false;
/**
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
*/
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; i++) {
// 前一个结束时间大于后一个开始时间
if (intervals[i][0] < intervals[i - 1][1]) {
returtn false;
}
}
return true;
}
拓展1：会议室II 253，给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
示例：
示例 1:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2
示例 2:
输入: [[7,10],[2,4]]
输出: 1
思路：有时间重叠的，肯定不能安排在一间会议室。还是需要先排序，这里按照会议的开始时间排序，这里使用小根堆（优先级队列）存储会议的结束时间（堆顶为会议最早结束时间）：
- 如果另一场会议的开始时间小于当前堆顶，说明会议时间冲突，我们需要再单独开一间（即当前会议的结束时间作为新的堆顶）；
- 否则，没有时间冲突，等这场会议结束使用。
代码：
import java.util.LinkedList;
class Solution {
public int minMeetingRooms(int[][] intervals) {
if(intervals == null || intervals.length == 0){
return 0;
}
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o1 - o2);
queue.offer(intervals[0][1]);
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] >= queue.peek()){
queue.poll();
}
queue.offer(intervals[i][1]);
}
return queue.size();
}
}
拓展2：最多可以参加的会议数目1353，给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。请你返回你可以参加的 最大 会议数目。
示例：
示例 1:
输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
思路：本题还是排序，注意题意，我们不是要把一个会议的所有天都在，只需要参加满足会议（在开始和结束之间参加）的一天即可，比较简单的是利用set存储已经占用的天数（因为同一天不能参加两个会议），但是超时。。。
可以使用优先级队列，将这一天能参加的会议的结束时间全部入堆，会议的起始时间 == day，这一天一定能参加（注意按照会议的开始时间排序）。为什么是结束时间？有点贪心思想，保证能参加最多的会议
- 我们一天一天安排，首先删除已经结束的会议（出堆），此时堆顶这一天是我们可以参加的会议（一天只能参加一场）！
代码：
class Solution {
// public int maxEvents(int[][] events) {
// Arrays.sort(events, (o1, o2) -> o1[1] - o2[1]);
// Set<Integer> set = new HashSet<>();
// for (int[] event : events) {
// for (int i = event[0]; i <= event[1]; ++i) {
// if (!set.contains(i)) {
// set.add(i);
// break;
// }
// }
// }
// return set.size();
// }
public int maxEvents(int[][] events) {
Arrays.sort(events, (o1, o2) -> o1[0] - o2[0]);
PriorityQueue<Integer> pq = new PriorityQueue<>();
int i = 0;
int day = 1;
int ans = 0;
int n = events.length;
while (i < n || !pq.isEmpty()) {
while (i < n && events[i][0] == day) {
pq.offer(events[i][1]);
i++;
}
while (!pq.isEmpty() && pq.peek() < day) {
pq.poll();
}
if (!pq.isEmpty()) {
pq.poll();
ans++;
}
day++;
}
return ans;
}
}
2.不重叠区间（435-medium）
题目描述：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
示例：
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
思路：为了保证移除最少的区间集合，即寻找最多的不重叠区间。贪心策略：保证每个区间尾越小，那么后边预留的空间越大。
- 可以通过对尾区间进行排序，遍历数组（记录不重叠个数
count），当前头小于上一个的尾，直接删除（重叠）, - 否则
count++，更新最小的尾区间end。
ps：注意起始边界处理，时间复杂度：O(nlogn)！
代码：
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); //1.每个子区间尾排序
int count = 1;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) continue; //2.与之前区间重叠(即当前区间的头小于之前区间的尾，删除)
end = intervals[i][1];
count++;
}
return intervals.length - count; //3.要删除的区间数量
}
3.合并区间（56-medium）
题目描述：给出一个区间的集合，请合并所有重叠的区间。
示例：
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路：实现合并区间肯定要进行排序。采用每个子区间左边界排序（右边界也可），然后从左向右遍历数组。注意：
- 若没有重叠（数组为空/当前区间的左边界，大于结果区间的右边界），不需合并则加入结果；
- 否则更新右边界生成新的区间加入结果，更新结果区间的右边界。
代码：
public int[][] merge(int[][] intervals) {
//1.按照每个子区间端点（左端点）进行排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[][] ret = new int[intervals.length][2];
int idx = -1;
for (int[] interval : intervals) {
//3.没有重叠（数组为空/当前区间左边界大于结果区间右边界），直接加入
if (idx == -1 || interval[0] > ret[idx][1]) {
ret[++idx] = interval;
} else {
//4.有重叠，合并区间(更新结果区间右边界)
ret[idx][1] = Math.max(interval[1], ret[idx][1]);
}
}
//ps：copyOf(int[] original, int newLength)
return Arrays.copyOf(ret, idx + 1);
}
4.插入区间（57-medium）
题目描述：给出一个无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
思路：因为原始数组已经排好序，并且不存在重叠，那么直接用索引i遍历数组，索引idx记录结果集索引，分三步走：
- 如果存在，将左边与新区间不重叠的部分直接接入结果（没影响的部分）；
- 新区间与区间存在重叠，合并区间（更新新区间左右边界），将更新后的新区间加入结果；通俗一点说：新区间的左边界<= 当前上一个区间的右边界，>= 下一个区间的左边界，我们需要将这三个区间合并（更新新区间的左右边界，加入结果）
- 如果存在，将右边与新区间不重叠的部分直接接入结果（没影响的部分）；
代码：
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] ret = new int[intervals.length + 1][2];
int idx = 0, i = 0;
//1.左边不重叠区间
while (i < intervals.length && newInterval[0] > intervals[i][1]) {
ret[idx++] = intervals[i++];
}
//2.区间合并(更新新区间的左右边界)
while (i < intervals.length && newInterval[1] >= intervals[i][0]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
ret[idx++] = newInterval;
//3.右边不重叠区间
while (i < intervals.length) {
ret[idx++] = intervals[i++];
}
return Arrays.copyOf(ret, idx);
}
总结
总结上述四个题目，主要可以细分为两类问题。
涉及区间重叠问题：
- 区间是否重叠（T252）
- 最多的的不重叠区间（T435）
涉及区间合并问题：
- 合并所有重叠区间（T56）
- 合并插入过程中可能引入的重叠区间（T57）
其实，上述问题都需要对区间端点进行排序，这里明确一点，不管是根据左端点排序还是右端点排序都是可以的。需要画图去看左右边界情况，比较直观。
