代码随想录算法训练营第三十一天|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;
    }
};

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

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

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

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;
    }
};

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：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;
    }
    
};