435. 无重叠区间
思路：
这道题可以先求出没有重叠的区间数目，然后与总数目做差就得到了需要去除的数目。在求没有重叠的数目之前可以先将数组排序，按照右区间排序，这样在遍历的时候就可用上一个元素的右端点与下一个元素的左端点比较来判断是否有重叠。
代码：
class Solution {
public:
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;
int end=intervals[0][1];
for(int i=1;i<intervals.size();i++)
{
if(end<=intervals[i][0])
{
end=intervals[i][1];
count++;
}
}
return intervals.size()-count;
}
};
763. 划分字母区间
思路：
这道题的难点在于如何划分区间，可以先将每个字母出现的最远位置记录下来，在遍历的过程中不断更新最远距离，如果最远距离与正在遍历的位置相同，则可以划分为一个区间。
代码：
class Solution {
public:
vector<int> partitionLabels(string s) {
int num[27]={0};
for(int i=0;i<s.size();i++)
{
num[s[i]-'a']=i;
}
vector<int> res;
int left=0;
int right=0;
for(int i=0;i<s.size();i++)
{
right=max(right,num[s[i]-'a']);
if(right==i)
{
res.push_back(right-left+1);
left=right+1;
}
}
return res;
}
};
56. 合并区间
思路：
这道题的思路和第435题一致，如果边界重叠了就继续延长右边界，直到不重叠为止。
代码：
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;
if(intervals.size()==0)return res;
sort(intervals.begin(),intervals.end(),cmp);
res.push_back(intervals[0]);
for(int i=0;i<intervals.size();i++)
{
if (res.back()[1] >= intervals[i][0]) {
res.back()[1] = max(res.back()[1], intervals[i][1]);
} else {
res.push_back(intervals[i]);
}
}
return res;
}
};
