题目1：435 无重叠区间

题目链接：435 无重叠区间

题意

intervals[i]=[starti，endi] 移除区间，使得区间互不重叠，返回移除区间的最小数量

相邻区间挨在一起，尽量移除重叠区间

代码

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        //左边界升序
        return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       sort(intervals.begin(),intervals.end(),cmp);
       int result = 0;
       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;
    }
};

• 时间复杂度：O(nlog n) ，有一个快排
• 空间复杂度：O(n)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间

题目2：763 划分字母区间

题目链接：763 划分字母区间

题意

将字符串划分为尽可能多的片段，使得同一字母最多出现在一个片段

将所有划分结果顺序连接，得到的字符串仍是s        返回每个字符串片段的长度

1）记录每个字符最远出现的位置

2）遍历字符串，字符最远出现位置与当前下标i相等，即为分割线

代码

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 left = 0;
        int right = 0;
        vector<int> result;
        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;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)，使用的hash数组是固定大小

题目3：56 合并区间

题目链接：56 合并区间

题意

合并所有重叠区间intervals[i]=[starti,endi]，返回不重叠的区间数组 边界值相等也视为重叠

合并区间时，先将元素放到数组中，再用下一个元素与数组中的当前元素比较，便于操作

代码

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<vector<int>> result;
        result.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            //重叠
            if(intervals[i][0]<=result.back()[1]){
                //合并右边界
                result.back()[1] = max(intervals[i][1],result.back()[1]);
            }
            //不重叠
            else{
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

• 时间复杂度: O(nlogn)
• 空间复杂度: O(logn)，排序需要的空间开销