题目链接：435. 无重叠区间
文章讲解：代码随想录 435. 无重叠区间讲解
视频讲解：贪心算法，依然是判断重叠区间 | LeetCode：435.无重叠区间
思路和解法
题目：
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
想法：
今天三道题用了三种不同的细节做法，一个是直接在原数组上更新，第二种是用left right记录，第三种是直接在结果数组上更新。第一题是自己AC掉的，照搬了昨天的做法。
class Solution {
public:
//自定义排序顺序
static bool cmp(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
//先按照每个小区间的起始位置排序
//遍历一遍，出现重叠就需要删除一个区间，但是删除哪个？要对比一下结束的位置，删掉结束位置靠后的那个区间
//用一个变量记录删除数量，需要删除时+1，同时每次删除时把当前区间的结束位置更新为结束位置靠前的那个值
//记录删除次数
int result = 0;
//忘记排序了
sort(intervals.begin(), intervals.end(), cmp);
//进行遍历
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
result++;
intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
}
}
return result;
}
};
题目链接：763.划分字母区间
文章讲解：代码随想录 763.划分字母区间讲解
视频讲解：贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间
思路和解法
题目：
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
想法：
因为要记录每个区间放入结束数组中，所以用left和right做记录。
class Solution {
public:
vector<int> partitionLabels(string s) {
//统计每个字符出现的最远位置 为什么要27？26不行吗？26也行 不知道为什么讲解里用27
int hash[26] = {
0};
for (int i = 0; i < s.size(); i++) {
hash[s[i] - 'a'] = i;
}
//再遍历一次 每次都更新当前区间出现字符的最远位置，用right记录，当遍历的位置和right相等时，
//说明前面这段区间可以划分为一个区间，而且是最短的区间，这样保证了尽可能多地划分区间
//用left记录区间起始位置，这样才能计算出区间长度存入结果数组，每次划分出一个区间更新一次left
vector<int> result;
int left = 0, 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 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
想法：
这道题自己想没理清楚，还想着要在原数组上改动还是用left right记录，结果讲解里直接更新结果数组，这种思路明显更符合习惯的思维方式。
class Solution {
public:
//我决定用和射气球类似的方法来写
//还是先排序，然后开始遍历，每次看和前一个区间是否有重叠，如果重叠就需要合并区间
//为了记录合并区间的结果，我还是用left和right记录区间的起始和结束位置，那么每次都先判断是否有重叠
//用当前区间的起始位置right比较，不重叠记录一次区间并更新left，重叠更新right为更远的结束位置
//以上是自己的思路，没理清楚直接看了讲解，发现讲解完全是另一个套路
vector<vector<int>> merge(vector<vector<int>>& intervals) {
//又忘记排序了 这次讲解也第一次用lambda表达式自定义排序规则
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
return a[0] < b[0];});
vector<vector<int>> result;
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
//当前区间起始位置<=前一个区间的结束位置就是重叠
if (result.back()[1] >= intervals[i][0]) {
//重叠就要更新右边界
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]);
}
}
return result;
}
};
