LeetCode435. 無重疊區間

和上題引爆氣球的邏輯非常像，只要想到左邊界排序之后，更新右邊界為最小值，則就可以輕松寫出代碼，如果按照右邊界來排序，則就可以省去取最小值的邏輯。

代碼如下：時間復雜度O(nlogn)；空間復雜度O(n)（快排）

class Solution {
public:static bool cmp(vector<int> a,vector<int> b){if(a[0]==b[0]) return a[1]<b[1];return a[0]<b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);int result = 0;for(int i=1;i<intervals.size();i++){if(intervals[i][0]<intervals[i-1][1]){result++;intervals[i][1] = min(intervals[i-1][1],intervals[i][1]);}}return result;}
};

LeetCode763.劃分字母區間

本題首先記錄每個字母最遠出現的下標，然后不斷遍歷字符，判斷是否到達最遠下標，如果達到，則該下標之前的字符串可以作為一個字串保留。

本題的妙處：哈希表儲存最遠下標；max值不斷維護最遠下標。

代碼如下:時間復雜度O(n)；空間復雜度O(1)哈希表為固定大小。

class Solution {
public:vector<int> partitionLabels(string s) {int hash[27]={0};vector<int> result;for(int i=0;i<s.size();i++){hash[s[i]-'a'] = i;}int end = hash[s[0]-'a'];int pre_end = 0;for(int i=0;i<s.size();i++){if(i==end){result.push_back(end+1-pre_end);pre_end = end+1;if(end==s.size()-1) break;end = hash[s[i+1]-'a'];}end = max(end,hash[s[i]-'a']);}return result;}
};

LeetCode56. 合并區間?

前面的題是在求交集，那么本題就是求并集，邏輯是一樣的，如果重疊，更新右邊界，不重疊，插入result數組中，左右邊界都更新。代碼如果簡潔點可以直接利用result.back()[1]這種形式進行操作。

代碼如下：時間復雜度O(nlogn)；空間復雜度O(n)（快排）。

class Solution {
public:static bool cmp(vector<int> a,vector<int> b){if(a[0]==b[0]) return a[1]<b[1];return a[0]<b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);vector<vector<int>> result;vector<int> interval(2,0);interval[0] = intervals[0][0];interval[1] = intervals[0][1];for(int i=1;i<intervals.size();i++){if(intervals[i][0]>interval[1]){result.push_back(interval);interval[0] = intervals[i][0];interval[1] = intervals[i][1];}else if(intervals[i][0]<=interval[1]){interval[1] = max(intervals[i][1],interval[1]);}}result.push_back(interval);return result;}
};