文章目录
435.无重叠区间
文章链接：435.无重叠区间
视频链接：贪心算法，依然是判断重叠区间 | LeetCode：435.无重叠区间
状态：排序顺序很重要！决定了我们如何处理后续逻辑。对于按右边界排序，我们只要抓住分割线即可，每次更新分割线，说明就有非交叉区间；
想都不用想，本题首先要求的肯定就是进行排序，让为了让我们后续更好进行操作。
并且可以很直观得推导出我们的贪心策略：
局部最优——当前区间与相邻两个区间是否重叠，这里是非常有技巧的，具体可以看下面的思路
全局最优——找出所有的重叠区间
按右边界排序
我们先按右边界进行排序，然后从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
在记录非交叉区间的个数也是很需要技巧的：
总之一句话，最重要的点就在于找到区间的分割线，每次遇到分割线，我们就记录一次非交叉区间个数。比如上文中，更新了两次分割线，所以非交叉区间是3。所以在代码表现上，也是比较直观的。
基于以上代码的一个重要前提就是：区间是按照右边界来排序的
CPP代码
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;
}
};
按左边界排序
对于左边界排序，这里拿 intervals = [[1,100],[11,22],[1,11],[2,12]]举例，
排序后：intervals = [[1,100],[1,11],[2,12],[11,22]]。如果我们按照右边界排序的处理还能行吗。简单推导一下，这样会导致我们的最终结果是3！因为end永远都无法更新，程序认为只有一条分割线，也就是count = 1。
那么如果按照左边界来排序应该怎么写呢？
如何判断相邻区间是否重叠
如果当前区间的左边界[1, 11]大于等于上一个区间的右边界[1, 100]。说明相邻区间不重叠，如果不满足该情况，那肯定说明区间重叠。
这里的count表示的是重叠区间的个数。
end在此处仍然表示的是区间分割点。
if (intervals[i-1][0] >= intervals[i][1]) end = intervals[i][1];
else {
count++; //记录我们重叠了多少个区间
}
如何判断一下一个区间与当前相邻区间是否重叠
要首先计算出之前我们判断的相邻区间的最小边界（左边界的最小值），和我们下一个区间的左边界是否重叠。
else {
count++;
end = min(end, intervals[i][1])
}
这里num[i][1]=min(nums[i-1][1], nums[i][1])，等到i遍历到下一个区间，应该和之前两个相邻区间的最小右边界比较，如果当前i区间的左边界要大的话，那么说明不是重叠区间。
总结
左边界的思想一句话就是：如果发现了重叠区间，我们就进行更新新的分割点，并且count++
CPP代码
class Solution {
public:
static bool cmp (const vector<int>& a, const 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 count = 0; // 注意这里从0开始，因为是记录重叠区间
int end = intervals[0][1]; // 记录区间分割点
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= end) end = intervals[i][1]; // 无重叠的情况
else { // 重叠情况
end = min(end, intervals[i][1]);
count++;
}
}
return count;
}
};
# 精简版
class Solution {
public:
static bool cmp (const vector<int>& a, const 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 count = 0; // 注意这里从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]);
count++;
}
}
return count;
}
};
763.划分字母区间
文章链接：763.划分字母区间
视频链接：贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间
状态：
本题其实就是一句话“面多了加水，水多了加面，直到刚刚好”。
这里完全不是贪心的思路，就是全局的一个模拟，主要它也属于重叠区间的问题。
思路
思路上还是很难想到的。
我们在遍历过程中，相当于找到每一个字母出现的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。
所以分为如下两步：
- 统计每个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
我们需要记录每个字符出现的最后位置，如图：
伪代码实现
- 统计每一个字符最后出现的位置
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;
}
}
CPP代码
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;
}
};
56. 合并区间
文章链接：56. 合并区间
视频链接：贪心算法，合并区间有细节！LeetCode：56.合并区间
状态：
思路
本题同样也是重叠区间的问题。
区别在于判断区间重叠后的逻辑，本题是将重叠区间进行合并。
先排序，如果intervals[i][0] <= intervals[i - 1][1]就有重叠，所以进行合并
合并的逻辑也比较简单，
用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
CPP代码
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;
}
};