總結下重疊區間問題

LC?452. 用最少數量的箭引爆氣球?

和

LC 435. 無重疊區間

本質上是一樣的。

LC?452. 用最少數量的箭引爆氣球 是求n個區間當中 ， 區間的種類數量 k。此處可以理解為，重疊在一起的區間屬于同一品種，沒有重疊的區間當然就是另一個品種 ， 最少數量的箭，也就是區間總的種類數量k ， 有k種區間 ，最少就得花k只劍，每種區間耗費一支。

而?LC 435. 無重疊區間 ， 問使得區間之間不重疊，要移除的區間數量，可以這樣思考：

n個區間當中，有k種區間（區間的種類數量 k）。要使得區間之間不重疊 ， 也就是說每個種類的區間只能保留一種！（因為有重疊的區間屬于同一個品種）

因此 要移除的區間數量 就是總的區間數 n 減去區間種類的數量 k。

這兩個題是同一個模板！

給出無重疊區間的代碼

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals , (a ,b) -> a[0] -b[0] );int count = 1;for(int i = 1 ; i < intervals.length ; i ++){if(intervals[i][0] >= intervals[i-1][1]){count ++;}else{intervals[i][1] = Math.min(intervals[i-1][1] , intervals[i][1]);}}return intervals.length - count;}
}

763.劃分字母區間

題目描述：

給你一個字符串?s?。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。例如，字符串?"ababcc"?能夠被分為?["abab", "cc"]，但類似?["aba", "bcc"]?或?["ab", "ab", "cc"]?的劃分是非法的。

思路：

1.先遍歷字符串 ，把每個字母出現的最大的索引存到一個哈希表中

2.再遍歷字符串，此時我們就要去劃分字符串了。劃分的過程如下：

先初始化子區間的左右邊界 left ， right 初始化為0 ， 0

遍歷的時候 ，動態更新當前區間的最大右邊界 ，而當恰好此時的索引 i 等于右邊界時 ，就劃分出一個子區間了，該子區間長度為 right - left + 1。 劃分完畢后 ，left 需要更新為 i + 1 ，然后繼續遍歷，重復此過程。。。。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> res = new ArrayList<>();int[] hash = new int[26];for(int i = 0 ; i < s.length() ; i ++){hash[s.charAt(i) - 'a'] = i;}int left = 0;int right = 0;for(int i = 0 ; i < s.length() ; i ++){right = Math.max(right , hash[s.charAt(i) - 'a']);if(i == right){res.add(right - left + 1);left = i + 1;}}return res;}
}

LC 56. 合并區間

本題是LC 452 , LC 435同源的題 ，區別在于這里要把合并后的區間輸出出來 ， 因此需要我們手動維護合并后的區間邊界 left 和 right。而之前可以不管這個動態變化的邊界 ，僅僅是計算count 。

寫代碼時要注意這一點，不能想當然的以為 right = max(nums[i][1] ， nums[i-1][1]) !!

class Solution {private List<int[]> temp = new ArrayList<>();public int[][] merge(int[][] intervals) {Arrays.sort(intervals , (a , b) ->(a[0] - b[0]));int left = intervals[0][0];int right = intervals[0][1];for(int i = 1 ; i < intervals.length ; i ++){if(intervals[i][0] > right){temp.add(new int[]{left , right});//只有當區間不重疊時， 才更新左邊界left = intervals[i][0];right = intervals[i][1];}else{//重疊了，由于左邊界本身是從小到大排序的，因此還是維持之前的leftright = Math.max(intervals[i][1] , right);}}temp.add(new int[]{left , right});int len = temp.size();int[][] res = new int[len][2];for(int i = 0 ; i < temp.size() ; i ++){res[i] = temp.get(i);}return res;}
}