一、前言：
参考文献：代码随想录
今天的主题是贪心算法中的重叠区间，就像昨天的扎气球问题，就是通过排序，然后将区间重叠起来，然后更具边界值判断这个区间是否重叠。
二、无重叠区间
1、思路：
这题的思路和昨天的思路很象，也可以说是一模一样。
（1）首先按照左边界进行排；
static bool cmp(const vector<int> &a, const vector<int> &b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
sort(intervals.begin(), intervals.end(), cmp);（2）这样排完序之后就大概是
昨天这样的情况；
（2）然后遍历intervals数组，找出重叠的区间，如果出现重叠的区间那就把找出来，找到一个就删除++就ok了；
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]);
wdelete++;
}
}2、整体代码如下：
class Solution {
private:
static bool cmp(const vector<int> &a, const vector<int> &b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
// 这里的重叠区间与昨日的边界有一个区别
// 就是两个边界相等时这也可看作不重叠
sort(intervals.begin(), intervals.end(), cmp);
int wdelete = 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]);
wdelete++;
}
}
return wdelete;
}
};三、划分字母区间
1、思路：
这一题主要考查的是对数组的应用以及一个核心思想，就是需要记录最远的字母的位置即可；
（1）首先遍历字符串，然后找到每一个字母的最远的边界值；
int hash[27] = {0}; // 统计字母最后出现的位置
for (int i = 0; i < s.size(); i++) {
hash[s[i] - 'a'] = i;
}（2）之后再次对字符串进行遍历，通过两个指针，去分割字符串，其中匹配的条件就是当i == right的时候就说明这个字符串已经到了最末尾的位置了，就可以划分了；
int right = 0;
int left = 0;
vector<int> result;
for (int i = 0; i < s.size(); i++) {
right = max(right, hash[s[i] - 'a']); // 存放字符出现最远的边界
if (right == i) {
result.push_back(right - left + 1);
left = right + 1;
}
}2、整体代码如下：
class Solution {
public:
vector<int> partitionLabels(string s) {
int hash[27] = {0}; // 统计字母最后出现的位置
for (int i = 0; i < s.size(); i++) {
hash[s[i] - 'a'] = i;
}
int right = 0;
int left = 0;
vector<int> result;
for (int i = 0; i < s.size(); i++) {
right = max(right, hash[s[i] - 'a']); // 存放字符出现最远的边界
if (right == i) {
result.push_back(right - left + 1);
left = right + 1;
}
}
return result;
}
};四、合并区间
1、思路：
这个思路和扎气球的差不多，但是这么不是贪最小范围，而是贪最大范围；
（1）首先还是对原有的数组进行排序；
static bool cmd(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
sort(intervals.begin(), intervals.end(), cmd);（2）然后就是设置两个边界，left和right，就设置为第一个数组的左右边界；
int left = intervals[0][0]; // 存储左边界临时变量
int right = intervals[0][1]; // 记住右边界的一个临时变量（3）之后遍历数组，如果当前数组的前边界大于right，说明已经不包含了，就可以将right和left存入到数组中去了；如果包含，那么就更新right，在right和 当前数组贪一个最大的即可；
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] > right) {
vector<int> a = {left, right};
result.push_back(a);
left = intervals[i][0];
right = intervals[i][1];
} else {
right = max(intervals[i][1], right);
}
}（4）最后遍历完成之后，就把最后的left和right进行回收即可；
result.push_back({left, right});2、整体代码如下：
class Solution {
private:
static bool cmd(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmd);
int left = intervals[0][0]; // 存储左边界临时变量
int right = intervals[0][1]; // 记住右边界的一个临时变量
vector<vector<int>> result;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] > right) {
vector<int> a = {left, right};
result.push_back(a);
left = intervals[i][0];
right = intervals[i][1];
} else {
right = max(intervals[i][1], right);
}
}
result.push_back({left, right});
return result;
}
};今日学习时间：1.5小时
leave message:
We are made wise not by the recollection of our past, but by the responsibility for our future.
我们之所以明智，不是因为我们对过去的回忆，，而是因为我们对未来的责任。
