无重叠区间
这道题按左边界排序和右边界排序都是可以的。主要就是要统计出不重合区间的数目。如果按照右区间排序，下面这张图十分形象：
这样去掉一组重叠区间后，剩下的那个区间它的右端点最小，能让后面产生尽量多的不重叠空间。
右区间排序写法：
class Solution{
static bool cmp(vector<int>& a, vector<int>& b){
return a[1] < b[1];
}
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals){
sort(intervals.begin(), intervals.end(), cmp);
int count = 1; //统计不重叠的区间数目，初始化为1，一定有一个不重叠的区间
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] >= intervals[i - 1][1]){ // 出现了一个新的不重叠区间
count++;
}
else intervals[i][1] = intervals[i - 1][1];
}
return intervals.size() - count;
}
};
左边界排序写法：
class Solution{
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] < b[0];
}
public:
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]){
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
// 其实效果和按右边界排序是一样的，只不过这里自己维护最小的右边界
result++;
}
}
return result;
}
};
需要注意一个问题，如果是统计不重叠的区间，那就是从1计数，若是统计重叠的区间，则是从0开始计数。
划分字母区间
相当于寻找每一个字母出现的边界，如果找到了之前所有出现字母的最远边界，说明这个边界就是一个分割点。
所以可以分为两步来处理：
- 找到每个字母出现的最远边界
- 重新遍历数组，更新遇到的字母出现的最远边界，如果当前遍历到下标与当前所有字母的最远边界相等，则找到了一个分割点。
class Solution{
public:
vector<int> partitionLabels(string s) {
int bound[26] = {0};
for(int i = 0; i < s.size(); i++){
bound[s[i] - 'a'] = i; // 记录每个字母出现的最远位置下标
}
int left = 0, right = INT_MIN;
vector<int> result;
for(int i = 0; i < s.size(); i++){
right = max(right, bound[s[i] - 'a']); // 更新当前遇到的字母出现的最远位置
if(i == right){
result.push_back(right - left + 1); // 当前到达的下标与最远边界相等，找到了一个分割点
left = i + 1;
}
}
return result;
}
};
与前几道区间题类似的，这道题可以记录每个字母的起止区间，然后将重叠的区间进行合并，得到的不重叠的区间就是满足条件的，可以让区间内的字母只出现在区间内。
class Solution {
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] < b[0];
}
public:
vector<vector<int>> computeBound(string s){
vector<vector<int>> intervals(26, vector<int>(2, 0));
for(int i = 0; i < s.length(); i++) {
int index = s[i] - 'a';
if(intervals[index][0] == 0){
intervals[index][0] = i + 1;
}
intervals[index][1] = i + 1;
}
vector<vector<int>> filtered;
for(int i = 0; i < intervals.size(); i++){
if(intervals[i][0] != 0){
filtered.push_back(intervals[i]);
}
}
return filtered;
}
vector<int> partitionLabels(string s) {
vector<vector<int>> intervals = computeBound(s);
sort(intervals.begin(), intervals.end(), cmp);
vector<int> result;
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] > intervals[i - 1][1]){
result.push_back(intervals[i - 1][1] - intervals[i - 1][0] + 1);
}
else{
intervals[i][0] = intervals[i - 1][0];
intervals[i][1] = max(intervals[i - 1][1], intervals[i][1]);
}
if(i == intervals.size() - 1){
// 但要注意的是这种写法中，因为到末端以后没有更大的下标出现，从而记录末端区间，需要对末端单独处理
result.push_back(intervals[i][1] - intervals[i][0] + 1);
}
}
return result;
}
};
合并区间
这道题与上一道题可以说一模一样了，要实现的就是合并区间，只不过这道题是要区间，上面那道是要区间长度。
class Solution{
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] < b[0];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals){
sort(intervals.begin(), intervals.end(), cmp);
result.push_back(intervals[0]); // 后续如果有重叠，继续更新右边界
for(int i = 0; i < intervals.size(); i++){
if(intervals[i][0] <= result.back()[1]){ // 如果重叠，更新右边界最大值
result.back()[1] = max(result.back()[1], intervals[i][1]);
}
else{
result.push_back(intervals[i]); // 不重叠，直接填入结果数组
}
}
return result;
}
};
或者我们也可以沿用上一道题的思路，同样是合并区间啦。
class Solution {
static bool cmp(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] <= intervals[i - 1][1]){
intervals[i][0] = intervals[i - 1][0];
intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
}
else{
result.push_back(intervals[i - 1]); // 注意这里添加i - 1
}
}
result.push_back(intervals[intervals.size() - 1]); // 同样末端单独处理
return result;
}
};
