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）
其实，上述问题都需要对区间端点进行排序，这里明确一点，不管是根据左端点排序还是右端点排序都是可以的。需要画图去看左右边界情况，比较直观。
