算法学习打卡day35｜贪心算法之重叠区间问题：435. 无重叠区间、763.划分字母区间、56. 合并区间

编程入门行业动态更新时间:2024-10-10 12:23:12

算法学习打卡day35｜贪心算法之重叠<a href=https://www.elefans.com/category/jswz/34/1766384.html style= 区间问题：435. 无重叠区间、763.划分字母区间、56. 合并区间"/>

算法学习打卡day35｜贪心算法之重叠区间问题：435. 无重叠区间、763.划分字母区间、56. 合并区间

重叠区间问题

除了以下三道题还有一个 452. 用最少数量的箭引爆气球，也属于重叠问题，可以看这里复习。

贪心之重叠问题处理套路

重叠问题基本都是给出一个二维数组，每个元素都包含子数组的begin和end，做题步骤如下：
1. 对数组整体进行排序
  - 那选择根据左边界排序还是选择根据右边界排序呢？
    - 其实都是可以通过的，只是写法稍微有点区别。
    - 对于引爆气球和无重叠区间这两道题，由于我们只需要找出重叠的个数即可，那么使用右边界排序是最好的，因为如果采用左边界排序去写，不仅在不重叠的时候需要修改end，而且在重叠时，也需要修改end为两个重叠区间的最小值，因为要根据这个最小值去判断，下一个区间是否还和这两个区间重叠，看代码：
```
int end = points[0][1];
for (int i = 1; i < points_size; ++i) {if (end < points[i][0]) {end = points[i][1];count++;} else {end = min(points[i][1], end);}
}
```
    - 采用右边界排序时，由于有重合时，end已经是二者最小的了，无需任何操作，代码写法如下
```
int end = points[0][1];for (int i = 1; i < points_size; ++i) {if (end < points[i][0]) {end = points[i][1];count++;}}
```
    - 对于合并区间这道题，则是采用区间左边界排序比较好，因为我们要把所有重复的区间合并到一起，那么我们在保存合并后的区间时，不仅要修改左边界，也要修改右边界，那么除了每次修改end，还要更改begin，代码对比如下：
      
      采用了右边界排序的写法：
```
results.push_back(intervals[0]);for (int i = 1; i < intervals_size; ++i) {if (results.back()[1] < intervals[i][0]) {results.push_back(intervals[i]);//不重叠就把当前元素push} else {results.back()[0] = min(results.back()[0], intervals[i][0]);  //如果重叠就合并两个区间,把result的最后一个元素右区间，改为最大值，以便i + 1去比较 results.back()[1] = intervals[i][1];}
}
```
      采用了左边界排序的写法:
```
results.push_back(intervals[0]);
for (int i = 1; i < intervals_size; ++i) {if (results.back()[1] < intervals[i][0]) {results.push_back(intervals[i]);//不重叠就把当前元素push} else {results.back()[1] = max(results.back()[1], intervals[i][1]);  //如果重叠就合并两个区间,把result的最后一个元素右区间，改为最大值，以便i + 1去比较 }
}
```
    - 对于划分字母区间这道题，如果套模版做也是可以做的，就是统计每个字符出现的开始和结束位置，这个统计结果其实就相当于另外几道题的输入了，需求就是从这些结果中找到没有重叠的区间子集！剩下的就是套用模版了。
2. 其实就是上面for循环里的逻辑了，让当前元素的左边界和前面区间的end比较，比end小那就是重叠了，该怎么处理结合实际题目添加，否则就是没有重叠。

435. 无重叠区间

力扣题目链接
题目描述：
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

思路：

贪心算法：和打爆气球一个思路，采用右边界写法，每次不重叠就更改end，然后count++，相对简单，直接套用上面模版写法即可。

代码实现：

static bool cmp(vector<int>& a, vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int count = 0, end = intervals[0][1];for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < end) {count++;} else {end = intervals[i][1];}}return count;

763.划分字母区间

力扣题目链接
题目描述：
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = “eccbbbbdec”
输出：[10]

思路：

先统计每个字符最后一次出现的位置，为什么要统计这个？因为我们每个字符串的右边界，其实是所有字符的最远位置的最大值
定义一个right用来表示字符串的右边界，从头遍历字符串，每次都更新right，当i走到right的时候，那此时从left到right区间就是符合条件的子串，right之后一定没有当前子串里的字符了。
把子串大小存到result，更新left和right，直到循环结束。

代码实现：

vector<int> partitionLabels(string s) {if (s.size() == 1) {return {1};}vector<int> vec(26, 0);//统计每个字符最后一次出现的下标for (int i = 0; i < s.size(); i++) {vec[s[i] - 'a'] = i;}int left = 0, right = 0;vector<int> result;    for (int i = 0; i < s.size(); i++) {right = max(vec[s[i] - 'a'], right);if (i == right) {result.push_back(right - left + 1);left = ++right;}}return result;
}

56. 合并区间

力扣题目链接
题目描述：
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：

套用重叠问题模版，本体是要合并重叠区间，而不是删除，那么合并后的区间需要左右边界都修改，而采用左边界排序时，遍历数组时就不用去修改左边界了，直接看代码

代码实现

vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> results;sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];});//排序, 采用了lambda表达式int intervals_size = intervals.size();results.push_back(intervals[0]);for (int i = 1; i < intervals_size; ++i) {if (results.back()[1] < intervals[i][0]) {results.push_back(intervals[i]);//不重叠就把当前元素push} else {results.back()[1] = max(results.back()[1], intervals[i][1]);  //如果重叠就合并两个区间,把result的最后一个元素右区间，改为最大值，以便i + 1去比较 }}return results;
}