1.會(huì)議室（252-easy）
題目描述：給定一個(gè)會(huì)議時(shí)間安排的數(shù)組 intervals 瘦材，每個(gè)會(huì)議時(shí)間都會(huì)包括開始和結(jié)束的時(shí)間 intervals[i] = [starti, endi] 庆聘，請(qǐng)你判斷一個(gè)人是否能夠參加這里面的全部會(huì)議缭黔，即判斷是否存在重疊區(qū)域！
示例：
輸入: intervals = [[0,30],[5,10],[15,20]]
輸出: false
解釋: 存在重疊區(qū)間，一個(gè)人在同一時(shí)刻只能參加一個(gè)會(huì)議。
思路：對(duì)每個(gè)會(huì)議時(shí)間按照開始時(shí)間排序（關(guān)鍵）侧漓。然后遍歷數(shù)組進(jìn)行判斷，如果前一個(gè)會(huì)議結(jié)束的時(shí)間大于后一個(gè)會(huì)議開始的時(shí)間（前一個(gè)還沒(méi)結(jié)束监氢，后一個(gè)就開始了）布蔗，則存在重疊區(qū)域。
代碼：
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++) {
// 前一個(gè)結(jié)束時(shí)間大于后一個(gè)開始時(shí)間
if (intervals[i][0] < intervals[i - 1][1]) {
returtn false;
}
}
return true;
}
拓展1：會(huì)議室II 253忙菠，給定一個(gè)會(huì)議時(shí)間安排的數(shù)組何鸡，每個(gè)會(huì)議時(shí)間都會(huì)包括開始和結(jié)束的時(shí)間 [[s1,e1],[s2,e2],…] (si < ei)，為避免會(huì)議沖突牛欢，同時(shí)要考慮充分利用會(huì)議室資源骡男，請(qǐng)你計(jì)算至少需要多少間會(huì)議室，才能滿足這些會(huì)議安排傍睹。
示例：
示例 1:
輸入: [[0, 30],[5, 10],[15, 20]]
輸出: 2
示例 2:
輸入: [[7,10],[2,4]]
輸出: 1
思路：有時(shí)間重疊的隔盛，肯定不能安排在一間會(huì)議室。還是需要先排序拾稳，這里按照會(huì)議的開始時(shí)間排序吮炕，這里使用小根堆（優(yōu)先級(jí)隊(duì)列）存儲(chǔ)會(huì)議的結(jié)束時(shí)間（堆頂為會(huì)議最早結(jié)束時(shí)間）：
- 如果另一場(chǎng)會(huì)議的開始時(shí)間小于當(dāng)前堆頂，說(shuō)明會(huì)議時(shí)間沖突访得，我們需要再單獨(dú)開一間（即當(dāng)前會(huì)議的結(jié)束時(shí)間作為新的堆頂）龙亲；
- 否則陕凹，沒(méi)有時(shí)間沖突，等這場(chǎng)會(huì)議結(jié)束使用鳄炉。
代碼：
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：最多可以參加的會(huì)議數(shù)目1353杜耙，給你一個(gè)數(shù)組 events，其中 events[i] = [startDayi, endDayi] 拂盯，表示會(huì)議 i 開始于 startDayi 佑女，結(jié)束于 endDayi 。
你可以在滿足 startDayi <= d <= endDayi 中的任意一天 d 參加會(huì)議 i 谈竿。注意团驱，一天只能參加一個(gè)會(huì)議。請(qǐng)你返回你可以參加的 最大 會(huì)議數(shù)目空凸。
示例：
示例 1:
輸入：events = [[1,2],[2,3],[3,4]]
輸出：3
解釋：你可以參加所有的三個(gè)會(huì)議嚎花。
安排會(huì)議的一種方案如上圖。
第 1 天參加第一個(gè)會(huì)議劫恒。
第 2 天參加第二個(gè)會(huì)議贩幻。
第 3 天參加第三個(gè)會(huì)議。
思路：本題還是排序两嘴，注意題意，我們不是要把一個(gè)會(huì)議的所有天都在族壳，只需要參加滿足會(huì)議（在開始和結(jié)束之間參加）的一天即可憔辫，比較簡(jiǎn)單的是利用set存儲(chǔ)已經(jīng)占用的天數(shù)（因?yàn)橥惶觳荒軈⒓觾蓚€(gè)會(huì)議），但是超時(shí)仿荆。贰您。。
可以使用優(yōu)先級(jí)隊(duì)列拢操，將這一天能參加的會(huì)議的結(jié)束時(shí)間全部入堆锦亦，會(huì)議的起始時(shí)間 == day，這一天一定能參加（注意按照會(huì)議的開始時(shí)間排序）令境。為什么是結(jié)束時(shí)間杠园？有點(diǎn)貪心思想，保證能參加最多的會(huì)議
- 我們一天一天安排舔庶，首先刪除已經(jīng)結(jié)束的會(huì)議（出堆）抛蚁，此時(shí)堆頂這一天是我們可以參加的會(huì)議（一天只能參加一場(chǎng)）！
代碼：
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.不重疊區(qū)間（435-medium）
題目描述：給定一個(gè)區(qū)間的集合惕橙，找到需要移除區(qū)間的最小數(shù)量瞧甩，使剩余區(qū)間互不重疊。
示例：
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后弥鹦，剩下的區(qū)間沒(méi)有重疊肚逸。
思路：為了保證移除最少的區(qū)間集合，即尋找最多的不重疊區(qū)間。貪心策略：保證每個(gè)區(qū)間尾越小朦促，那么后邊預(yù)留的空間越大膝晾。
- 可以通過(guò)對(duì)尾區(qū)間進(jìn)行排序，遍歷數(shù)組（記錄不重疊個(gè)數(shù)
count）思灰，當(dāng)前頭小于上一個(gè)的尾玷犹，直接刪除（重疊）, - 否則
count++，更新最小的尾區(qū)間end洒疚。
ps：注意起始邊界處理歹颓，時(shí)間復(fù)雜度：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.每個(gè)子區(qū)間尾排序
int count = 1;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) continue; //2.與之前區(qū)間重疊(即當(dāng)前區(qū)間的頭小于之前區(qū)間的尾油湖，刪除)
end = intervals[i][1];
count++;
}
return intervals.length - count; //3.要?jiǎng)h除的區(qū)間數(shù)量
}
3.合并區(qū)間（56-medium）
題目描述：給出一個(gè)區(qū)間的集合巍扛，請(qǐng)合并所有重疊的區(qū)間。
示例：
輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
輸入: intervals = [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間乏德。
思路：實(shí)現(xiàn)合并區(qū)間肯定要進(jìn)行排序撤奸。采用每個(gè)子區(qū)間左邊界排序（右邊界也可），然后從左向右遍歷數(shù)組喊括。注意：
- 若沒(méi)有重疊（數(shù)組為空/當(dāng)前區(qū)間的左邊界胧瓜，大于結(jié)果區(qū)間的右邊界），不需合并則加入結(jié)果郑什；
- 否則更新右邊界生成新的區(qū)間加入結(jié)果府喳，更新結(jié)果區(qū)間的右邊界。
代碼：
public int[][] merge(int[][] intervals) {
//1.按照每個(gè)子區(qū)間端點(diǎn)（左端點(diǎn)）進(jìn)行排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[][] ret = new int[intervals.length][2];
int idx = -1;
for (int[] interval : intervals) {
//3.沒(méi)有重疊（數(shù)組為空/當(dāng)前區(qū)間左邊界大于結(jié)果區(qū)間右邊界）蘑拯，直接加入
if (idx == -1 || interval[0] > ret[idx][1]) {
ret[++idx] = interval;
} else {
//4.有重疊钝满，合并區(qū)間(更新結(jié)果區(qū)間右邊界)
ret[idx][1] = Math.max(interval[1], ret[idx][1]);
}
}
//ps：copyOf(int[] original, int newLength)
return Arrays.copyOf(ret, idx + 1);
}
4.插入?yún)^(qū)間（57-medium）
題目描述：給出一個(gè)無(wú)重疊的 ，按照區(qū)間起始端點(diǎn)排序的區(qū)間列表申窘。在列表中插入一個(gè)新的區(qū)間弯蚜，你需要確保列表中的區(qū)間仍然有序且不重疊（如果有必要的話，可以合并區(qū)間）剃法。
示例：
輸入：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]]
解釋：這是因?yàn)樾碌膮^(qū)間 [4,8] 與 [3,5],[6,7],[8,10] 重疊碎捺。
思路：因?yàn)樵紨?shù)組已經(jīng)排好序，并且不存在重疊玄窝，那么直接用索引i遍歷數(shù)組牵寺，索引idx記錄結(jié)果集索引，分三步走：
- 如果存在恩脂，將左邊與新區(qū)間不重疊的部分直接接入結(jié)果（沒(méi)影響的部分）帽氓；
- 新區(qū)間與區(qū)間存在重疊，合并區(qū)間（更新新區(qū)間左右邊界）俩块，將更新后的新區(qū)間加入結(jié)果黎休；通俗一點(diǎn)說(shuō)：新區(qū)間的左邊界<= 當(dāng)前上一個(gè)區(qū)間的右邊界浓领，>= 下一個(gè)區(qū)間的左邊界，我們需要將這三個(gè)區(qū)間合并（更新新區(qū)間的左右邊界势腮，加入結(jié)果）
- 如果存在联贩，將右邊與新區(qū)間不重疊的部分直接接入結(jié)果（沒(méi)影響的部分）；
代碼：
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] ret = new int[intervals.length + 1][2];
int idx = 0, i = 0;
//1.左邊不重疊區(qū)間
while (i < intervals.length && newInterval[0] > intervals[i][1]) {
ret[idx++] = intervals[i++];
}
//2.區(qū)間合并(更新新區(qū)間的左右邊界)
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.右邊不重疊區(qū)間
while (i < intervals.length) {
ret[idx++] = intervals[i++];
}
return Arrays.copyOf(ret, idx);
}
總結(jié)
總結(jié)上述四個(gè)題目捎拯，主要可以細(xì)分為兩類問(wèn)題泪幌。
涉及區(qū)間重疊問(wèn)題：
- 區(qū)間是否重疊（T252）
- 最多的的不重疊區(qū)間（T435）
涉及區(qū)間合并問(wèn)題：
- 合并所有重疊區(qū)間（T56）
- 合并插入過(guò)程中可能引入的重疊區(qū)間（T57）
其實(shí)，上述問(wèn)題都需要對(duì)區(qū)間端點(diǎn)進(jìn)行排序署照，這里明確一點(diǎn)祸泪，不管是根據(jù)左端點(diǎn)排序還是右端點(diǎn)排序都是可以的。需要畫圖去看左右邊界情況建芙，比較直觀没隘。
