算法知识点———

算法知识点————贪心

贪心：只考虑局部最优解，不考虑全部最优解。有时候得不到最优解。
DP：考虑全局最优解。DP的特点：无后效性（正在求解的时候不关心前面的解是怎么求的）；
二者都是在求最优解的，都有最优子结构的性质（子问题的最优解构成当前问题的最优解）。
经典的区间分割问题
1、无重叠区间

思路：如果当前区间的左端点大于等于前一个区间的右端点，说明当前区间可以是一个独立的区间，我们可以保存它，如果当前区间的左端点小于前一个区间的右端点，说明当前区间和前面一个区间重合了，我们需要删除一个区间，那么删除哪个更好呢？很明显是当前这个，因为下一个区间如果和前面那个区间重合了，也肯定和当前区间重合，这时候又要删除一个区间，但是下一个区间如果和当前区间重合，那么把当前区间删除后，不一定会和前面的区间重合。所以不论是Case 2还是Case 3我们都应该删除current区间。因此我们只需要不断的维护前一个保留区间的右端点即可，只有当当前区间的左端点大于前一个保留区间右端点时，我们才更新保留区间。
在这里插入图片描述

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int len = intervals.size();if(len == 1) return 0;sort(intervals.begin(),intervals.end(),[](const auto& u,const auto& v){return u[1] < v[1];});int base = intervals[0][1];//第一个里面的右边界int cnt = 1;for(int i=1;i<len ;i++){// 若当前区间与最近区间没有重叠，则移动到当前区间进行后续判定（之后的区间不可能与最近区间重叠）// 若当前区间与最近区间重叠，则删除二者中右边界更靠后的if(intervals[i][0] >= base){cnt++;            //统计非重叠的区间数量base = intervals[i][1];}}return len - cnt;}
};
//排序规则：
//先对右边界排序，右边界相同的时候左边界大的排在前面

区间合并类型的问题一般都要对左端点或者右端点进行排序，然后再进行区间的合并就方便了，因为左端点或者右端点已经有序了。
对这道题来说前后紧挨着的区间的相对位置关系只有3种：
对这道题来说前后紧挨着的区间的相对位置关系只有3种：
1.  st1             ed1    两区间相互包含st2    ed22.  st1        ed1         两区间不完全包含但有交叉st2         ed23.  st1        ed1         两区间完全没有交集st2        ed24. 不会出现这种情况      st1       ed1     因为之前对区间的左端点排过序了，后面区间的左端点不st2        ed2          可能超过前面区间的左端点最多相同。

2、合并区间：//按照左边界排序

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(),intervals.end(),[](const vector<int>& a,const vector<int>& b){if(a[0] == b[0]) return a[1] < b[1]; //左边界相等时按右边界排return a[0] < b[0] ;//先按照左边界排序});//记录新区间的左右端点，判断当前区间能否合并int left = intervals[0][0],right = intervals[0][1];for(auto interval : intervals){//当前区间左端点小于当前右边界，合并，并更新可能增大的右边界//当前区间左端点大于当前右边界，记录新的区间，进入下一个新区间构建if(interval[0] <= right && interval[1] > right){right = interval[1];continue;}if(interval[0] > right){res.push_back({left,right});left = interval[0];right = interval[1];}}res.push_back({left,right});//添加最后一个区间return res;}
};
//按照左边界排序

3、区间列表的交集

两个指针分别指向列表区间的开头
每次求得两个区间的交集(左端点取max,右端点取min)
每次将右端点靠后的区间指针向后移动。比较的时候舍弃右边界小的
在这里插入图片描述

class Solution {
public:vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {int len1 = firstList.size();int len2 = secondList.size();vector<vector<int>> res;int i =0,j =0;while(i < len1 && j < len2){int l = max (firstList[i][0],secondList[j][0]);int r = min(firstList[i][1],secondList[j][1]);if(l <= r) res.push_back({l,r});if(firstList[i][1] == secondList[j][1]) {i++;j++;} else if(firstList[i][1] < secondList[j][1]) i++;else j++;}return res;}
};