一遍過(guò)。首先把區(qū)間按左端點(diǎn)排序，然后右端點(diǎn)有兩種情況。

假設(shè)是a區(qū)間，b區(qū)間。。。這樣排列的順序，那么

假設(shè)a[1]>b[0],如果a[1]>b[1]，就應(yīng)該以b[1]為準(zhǔn)，否則以a[1]為準(zhǔn)。

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

?題解方法：

我來(lái)按照右邊界排序，從左向右記錄非交叉區(qū)間的個(gè)數(shù)。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個(gè)數(shù)就是需要移除的區(qū)間個(gè)數(shù)了

就是取 區(qū)間1 和 區(qū)間2 右邊界的最小值，因?yàn)檫@個(gè)最小值之前的部分一定是 區(qū)間1 和區(qū)間2 的重合部分，如果這個(gè)最小值也觸達(dá)到區(qū)間3，那么說(shuō)明 區(qū)間 1，2，3都是重合的。

接下來(lái)就是找大于區(qū)間1結(jié)束位置的區(qū)間，是從區(qū)間4開(kāi)始。那有同學(xué)問(wèn)了為什么不從區(qū)間5開(kāi)始？別忘了已經(jīng)是按照右邊界排序的了。

區(qū)間4結(jié)束之后，再找到區(qū)間6，所以一共記錄非交叉區(qū)間的個(gè)數(shù)是三個(gè)。

總共區(qū)間個(gè)數(shù)為6，減去非交叉區(qū)間的個(gè)數(shù)3。移除區(qū)間的最小數(shù)量就是3。

class Solution {
public:// 按照區(qū)間右邊界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 記錄非交叉區(qū)間的個(gè)數(shù)int end = intervals[0][1]; // 記錄區(qū)間分割點(diǎn)for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};

?

看了題解。

在遍歷的過(guò)程中相當(dāng)于是要找每一個(gè)字母的邊界，如果找到之前遍歷過(guò)的所有字母的最遠(yuǎn)邊界，說(shuō)明這個(gè)邊界就是分割點(diǎn)了。此時(shí)前面出現(xiàn)過(guò)所有字母，最遠(yuǎn)也就到這個(gè)邊界了。

可以分為如下兩步：

• 統(tǒng)計(jì)每一個(gè)字符最后出現(xiàn)的位置
• 從頭遍歷字符，并更新字符的最遠(yuǎn)出現(xiàn)下標(biāo)，如果找到字符最遠(yuǎn)出現(xiàn)位置下標(biāo)和當(dāng)前下標(biāo)相等了，則找到了分割點(diǎn)

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

?

一遍過(guò)。將區(qū)間按左端點(diǎn)從小到大排序。假設(shè)是排序后是a，b，。。。

假設(shè)b區(qū)間左端點(diǎn)b[0]小于等于a區(qū)間右端點(diǎn)a[1]，有兩種情況：1、a[1]<b[1]，那么合并區(qū)間選擇b[1]。2、a[1]>b[1]，就選a[1]，而合并區(qū)間左端點(diǎn)始終選擇a[0];

假設(shè)b[0]>a[1]，那么就可以把上次融合后的區(qū)間加入結(jié)果。

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

?題解寫(xiě)法：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 區(qū)間集合為空直接返回// 排序的參數(shù)使用了lambda表達(dá)式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一個(gè)區(qū)間就可以放進(jìn)結(jié)果集里，后面如果重疊，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 發(fā)現(xiàn)重疊區(qū)間// 合并區(qū)間，只更新右邊界就好，因?yàn)閞esult.back()的左邊界一定是最小值，因?yàn)槲覀儼凑兆筮吔缗判虻膔esult.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 區(qū)間不重疊 }}return result;}
};