代码随想录算法训练营第三十一天|435. 无重叠区间， 763.划分字母区间， 56. 合并区间

本文介绍: 首先需要对interval s 排序，以每个数组的右边界排序，再将第一个数组的右边界作为起始点，循环比较前数组的右边界和后数组的左边界。首先按照数组的左边界排序，再比较前数组后边界和后数组的前边界，如果包含，就就将后数组的后边界和前数组前边界当成合成的区间，如果不包含，当前数组没有其他数组包含它，直接加入结果数组。②两个数组存在包含关系。明确一点，如果前一个数组的右边界大于后一个数组的左边界就算重叠，利用这个统计不重叠的数组个数，剩下的就是重叠的个数。一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

435. 无重叠区间 – 力扣（LeetCode）

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

示例 1:

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

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

思路：明确一点，如果前一个数组的右边界大于后一个数组的左边界就算重叠，利用这个统计不重叠的数组个数，剩下的就是重叠的个数。

解决：首先需要对int e r vals排序，以每个数组的右边界排序，再将第一个数组的右边界作为起始点，循环比较前数组的右边界和后数组的左边界。最后用全部数组个数减去统计的不重叠个数就是需要移除的数组个数。

代码：

class Solution {
public:
    static bool cmp (vector&lt;int&gt;&amp; a,vector&lt;int&gt;&amp; b){
        return a[1]<b[1];
    }
    int eraseOverlapIntervals(vector<vector<int&gt;>&amp; intervals) {
        if(intervals.size()==0) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        int r=1;
        int end=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(end<=intervals[i][0]){
                end=intervals[i][1];
                r++;
            }
        }
        return intervals.size()-r;
    }
};

763. 划分字母区间 – 力扣（LeetCode）

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

思路：把同一字母最多出现在一个片段中，相当是找一个范围包含所有的之前出现过的字母，这个范围应该尽可能小。

解决：先统计每个字母最后出现的位置，再依次遍历每个元素，更新当前已经遍历过的元素中最远边界，如果当前元素的最后出现的位置小于最远边界，说明目前范围没有包含所有元素。直达字符最远出现位置下标和当前下标相等了，则找到了。找到以后，记录当前遍历的范围个数,right–left+1，同时更新范围的左边界left=i+1；

代码：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int h[27]={0};
        for(int i=0;i<s.size();i++){
            int num=s[i] - 'a';
            h[num]=i;
        }
        vector<int> r;
        int right=0;
        int left=0;
        for(int i=0;i<s.size();i++){
            right=max(right,h[s[i] - 'a'] );
            if(i==right){
                r.push_back(right-left+1);
                left=i+1;
            }
        }
        return r;
    }
};

56. 合并区间 – 力扣（LeetCode）

以数组 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].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路：明确什么情况下两个区间可以合并：①前一个数组的右边界在后一个数组左右边界之内；②两个数组存在包含关系。之后合并的区间左右边界数值也会因情况不同而改变。

解决：首先按照数组的左边界排序，再比较前数组后边界和后数组的前边界，如果包含，就就将后数组的后边界和前数组前边界当成合成的区间，如果不包含，当前数组没有其他数组包含它，直接加入结果数组。

代码：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>&amp; intervals) {
        vector<vector<int>> r;
        if(intervals.size()==0) return r;
        sort(intervals.begin(),intervals.end(),[](const vector<int>&amp; a,const vector<int>&amp; b){
           return a[0]<b[0];//按左边界排序
        });
        r.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(r.back()[1]>=intervals[i][0]){//前数组右边界大于后数组左边界,r.back()[1]取r中最后一维数组的右边界
                r.back()[1]=max(r.back()[1],intervals[i][1]);//更新当前合并区间的右边界
            }else{
            r.push_back(intervals[i]);
            }
        }
        return r;
    }
    
};