區(qū)間問(wèn)題
Ⅰ 解題框架
? 所謂區(qū)間問(wèn)題，就是線段問(wèn)題，讓你合并所有線段、找出線段的交集等等。主要有兩個(gè)技巧：
? 1、排序。常見(jiàn)的排序方法就是按照區(qū)間起點(diǎn)排序，或者先按照起點(diǎn)升序排序，若起點(diǎn)相同，則按照終點(diǎn)降序排序。
? 2、畫(huà)圖。就是說(shuō)不要偷懶，勤動(dòng)手，兩個(gè)區(qū)間的相對(duì)位置到底有幾種可能，不同的相對(duì)位置我們的代碼應(yīng)該怎么去處理。
Ⅱ 相關(guān)習(xí)題
1、刪除覆蓋區(qū)間（LeetCode 1288）
? 給你一個(gè)區(qū)間列表，請(qǐng)你刪除列表中被其他區(qū)間所覆蓋的區(qū)間。只有當(dāng) c <= a 且 b <= d 時(shí)，我們才認(rèn)為區(qū)間 [a,b) 被區(qū)間 [c,d) 覆蓋。在完成所有刪除操作后，請(qǐng)你返回列表中剩余區(qū)間的數(shù)目。
? 首先排序：按照起點(diǎn)升序排序，起點(diǎn)相同則按照終點(diǎn)降序排序，使用lamda表達(dá)式
//將intervals按照起點(diǎn)升序排序，起點(diǎn)相同則按照終點(diǎn)降序排序
Arrays.sort(intervals,(a,b)->{
if (a[0] == b[0]) return b[1]-a[1];
return a[0]-b[0];
});
排序之后，兩個(gè)相鄰區(qū)間只可能有如下三種相對(duì)位置：
? 對(duì)于這三種情況，我們應(yīng)該這樣處理：對(duì)于情況一，找到了覆蓋區(qū)間。對(duì)于情況二，兩個(gè)區(qū)間可以合并，成一個(gè)大區(qū)間。對(duì)于情況三，兩個(gè)區(qū)間完全不相交。
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
int num = intervals.length;
//將intervals按照起點(diǎn)升序排序，起點(diǎn)相同則按照終點(diǎn)降序排序
Arrays.sort(intervals,(a,b)->{
if (a[0] == b[0]) return b[1]-a[1];
return a[0]-b[0];
});
//記錄線段的左右邊界，初始值就是第一條線段的起點(diǎn)和終點(diǎn)
int left = intervals[0][0];
int right = intervals[0][1];
//開(kāi)始覆蓋
for (int i=1;i<intervals.length;i++) {
if (intervals[i][1] <= right) { //區(qū)間被覆蓋了，對(duì)應(yīng)情況1
num--;
}else if (intervals[i][0] >= right) {//對(duì)應(yīng)情況3
left = intervals[i][0];
right = intervals[i][1];
}else if (right>intervals[i][0] && right<intervals[i][1]) {
//對(duì)應(yīng)情況2
right = intervals[i][1];
}
}
return num;
}
}
2、區(qū)間合并（LeetCode 56）
? 和第一題類(lèi)似，但要注意三種情況的符號(hào)，弄清楚到底要不要加等于號(hào)
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
List<int[]> res = new ArrayList<>();
//排序
Arrays.sort(intervals,(a,b)-> {
return a[0] == b[0]?(b[1]-a[1]):(a[0]-b[0]);
});
int left = intervals[0][0];
int right = intervals[0][1];
res.add(intervals[0]);
for (int i=1;i<len;i++) {
if (right >= intervals[i][1]) {
continue;
}else if(right >= intervals[i][0] && right < intervals[i][1]) {
right = intervals[i][1];
//先取出修改后再重新添加
int[] tmp = res.remove(res.size()-1);
tmp[1] = right;
res.add(tmp);
} else if (right < intervals[i][0]) { //注意此處為嚴(yán)格小于號(hào)，不能寫(xiě)小于等于！
left = intervals[i][0];
right = intervals[i][1];
int[] tmp2 = {left,right};
res.add(tmp2);
}
}
return res.toArray(new int[res.size()][]);
}
}
3、區(qū)間交集問(wèn)題（LeetCode 986）
? 給定兩個(gè)由一些 閉區(qū)間 組成的列表，每個(gè)區(qū)間列表都是成對(duì)不相交的，并且已經(jīng)排序。返回這兩個(gè)區(qū)間列表的交集。形式上，閉區(qū)間 [a, b]（其中 a <= b）表示實(shí)數(shù) x 的集合，而 a <= x <= b。兩個(gè)閉區(qū)間的交集是一組實(shí)數(shù)，要么為空集，要么為閉區(qū)間。例如，[1, 3] 和 [2, 4] 的交集為 [2, 3]。）
? 此題注意簡(jiǎn)化，不然情況太多
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
int lenA = A.length;int lenB = B.length;
if (lenA == 0 || lenB == 0) return new int[0][0];
int indexA = 0;int indexB = 0;
List<int[]> res = new ArrayList<>();
while (indexA < lenA && indexB <lenB) {
//可以這樣簡(jiǎn)化?。。? int lo = Math.max(A[indexA][0],B[indexB][0]);
int hi = Math.min(A[indexA][1],B[indexB][1]);
if (lo<=hi) {
res.add(new int[]{lo,hi});
}
//誰(shuí)的右邊小，誰(shuí)的指針就右移
if (A[indexA][1]>=B[indexB][1]) {
indexB++;
}else {
indexA++;
}
}
return res.toArray(new int[res.size()][]);
}
}
區(qū)間貪心算法
4、無(wú)重疊區(qū)間（LeetCode 435）
給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。
注意:可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒(méi)有相互重疊。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
return intervals.length-interval(intervals);
}
int interval (int[][] intervals) {
int res = 1;
Arrays.sort(intervals,(a,b)->{
return a[1]-b[1];
});
int start = intervals[0][0];
int end = intervals[0][1];
for (int i=1;i<intervals.length;i++) {
if (end <= intervals[i][0]) {
res++;
start = intervals[i][0];
end = intervals[i][1];
}
}
return res;
}
}
5、用箭引爆氣球（LeetCode 452）
與上一題不同的是兩個(gè)區(qū)間交集為一個(gè)點(diǎn)時(shí)還是算作一個(gè)區(qū)間
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points,(a,b)->{
//不要用return a[1]-b[1]; 會(huì)發(fā)生溢出
return a[1] > b[1] ? 1 : -1;
});
int res = 1;
int start = points[0][0];
int end = points[0][1];
for (int i=1;i<points.length;i++) {
if (end < points[i][0]) {
res++;
start = points[i][0];
end = points[i][1];
}
}
return res;
}
}
