无重叠区间
leetcode：435. 无重叠区间
贪心法
思路
去掉最少的区间数就是最少重叠区间对的个数。（成对的算，因为一对里面需要去掉一个）
类似射气球的处理方式。
左边界法：
-
按左边界从小到大排序。
-
遍历每个元素。取当前元素右边界为right判断是否重叠。
如果
[i]right > [i+1]left，重叠，再判断是否[i]right > [i+1]right，如果是，右边界更新。（总是更新为一对重叠区间里最小的）重叠统一i++（继续判断下一个），count++（重叠区间对多一个）。
复杂度分析
时间复杂度：O(NlogN)。
空间复杂度：O(logN)。（排序）
注意点
略
代码实现
左区间排序法：
class Solution {
public:
// 计算重叠区间个数
static bool cmp(vector<int>& a,vector<int>& b){
return a[0] < b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int count = 0;
for(int i = 0;i < intervals.size();i++){
int right = intervals[i][1];
while(i < intervals.size() - 1 && right > intervals[i + 1][0] ){
if(right > intervals[i+1][1]) right = intervals[i + 1][1];
count++;
i++;
}
}
return count;
}
};
划分字母区间
leetcode：763. 划分字母区间
贪心法
思路
-
遍历一遍s，建立出现最远下标映射表（数组）
-
根据区间遍历，遍历过程中更新区间右边界为区间内最远下标，
如果遍历到了区间右边界，说明已经实现了区间字符只出现在区间内，收获结果（区间长度）
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。26个字母的映射数组。
注意点
略
代码实现
class Solution {
public:
// 1. 遍历一遍s，建立出现最远下标映射表（数组）
// 2. 根据区间遍历，遍历过程中更新区间右边界为区间内最远下标，
// 如果遍历到了区间右边界，说明已经实现了区间字符只出现在区间内，收获结果（区间长度）
vector<int> partitionLabels(string s) {
vector<int> result;
int hash[27] = {0};
for(int i = 0;i < s.size();i++) hash[s[i] - 'a'] = i;
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; // 更新left
}
}
return result;
}
};
合并区间
leetcode：56. 合并区间
贪心法
思路
和射气球、无重叠区间类似，只是右边界每次更新为最大值。
-
按左边界从小到大排序。
-
遍历记录当前元素左右边界。
循环处理
right > intervals[i+1][0]，重叠的情况，每次更新right为两者最大值。直到不再重叠时，收获left、right结果。
复杂度分析
时间复杂度：O(NlogN)。排序
空间复杂度：O(N)。（最差情况下N个元素都不重叠，结果集N个元素）
注意点
略
代码实现
class Solution {
public:
// 排序
// 如果有重叠，更新
static bool cmp(vector<int>& a,vector<int>& b){
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> temp;
int left = 0;
int right = 0;
for(int i = 0;i < intervals.size();i++){
temp.clear();
left = intervals[i][0];
right = intervals[i][1];
while(i < intervals.size() - 1 && right >= intervals[i + 1][0]){
right = max(right,intervals[i+1][1]);
i++;
}
temp.push_back(left);
temp.push_back(right);
result.push_back(temp);
}
return result;
}
};