435. 無重疊區間 - 力扣（LeetCode）

class Solution
{
private:static bool cmp(const vector<int> &a,const vector<int> &b){if(a[0]==b[0]) return a[1]<b[1];return a[0]<b[0];}
public:int eraseOverlapIntervals(vector<vector<int>> &intervals){if(intervals.size()==0) return 0;sort(intervals.begin(),intervals.end(),cmp);int nums=0;vector<vector<int>> last;last.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(last[0][1]>intervals[i][0]){nums++;last[0]=last[0][1]>intervals[i][1]?intervals[i]:last[0];}else{last[0]=intervals[i];}}return nums;}
};

和昨天的社保氣球很像，按照那個思路寫了一下，發現還是有些案例不能通過。

最后發現是想的太簡單了，沒有考慮到后面的區間包含的范圍比前面的區間小的情況，從而不能找出最小區間，導致不能找到最小刪除次數。

題目鏈接：763. 劃分字母區間 - 力扣（LeetCode）

class Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0}; // i為字符，hash[i]為字符出現的最后位置for (int i = 0; i < S.size(); i++) { // 統計每一個字符最后出現的位置hash[S[i] - 'a'] = i;}vector<int> result;int left = 0;int right = 0;for (int i = 0; i < S.size(); i++) {right = max(right, hash[S[i] - 'a']); // 找到字符出現的最遠邊界if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}
};

用一個數組來表示出現過字符的最遠位置。

當右邊界right==最遠位置就可以把他放進答案里面了。

題目鏈接：56. 合并區間 - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 區間集合為空直接返回// 排序的參數使用了lambda表達式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一個區間就可以放進結果集里，后面如果重疊，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 發現重疊區間// 合并區間，只更新右邊界就好，因為result.back()的左邊界一定是最小值，因為我們按照左邊界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 區間不重疊 }}return result;}
};