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

目录

题目链接： 435. 无重叠区间

思路

代码

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

思路

代码

题目链接：56. 合并区间

思路

代码

总结

题目链接：435. 无重叠区间

思路

        首先还是按照区间的左端点进行排序，然后判断当前区间的左端点与上一个区间的右端点的大小来判断是否重叠。如果重叠，计数加一，并且更新当前区间的右端点为两个区间右端点的最小值。更新是为了比较下一个区间与上一个区间是否有重叠。（当前区间的前后两个区间）

代码

class Solution {
public:
    // 排序规则，按照左端点从小到大
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0)
            return 0;
        sort(intervals.begin(), intervals.end(), cmp); // 排序
        int count = 0; // 用来计数重叠区间
        for (int i = 1; i < intervals.size(); i++) {
            // 当前区间的左端点比上一个区间的右端点大
            // 即区间不重叠，继续
            if (intervals[i][0] >= intervals[i - 1][1]) {
                continue;
            }
            // 重叠时
            else {
                count++; // 重叠区间数量加一
                // 取两个重叠区间右端点的最小值为当前区间右端点
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return count;
    }
};

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

思路

        既然划分的区间要包含所有已经出现过的字母，所以一次遍历肯定不行。首先遍历记录信息，其实就是每个字母出现位置的最大下标；然后再次遍历数组，记录左右端点，左端点初始化在字符串开始，右端点不断更新为当前下标与前字母记录的下标二者之间的最大值。当二者相等时，说明找到一个区间。更新左端点为下一个位置，直至字符串遍历结束。

代码

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
            right = max(right, hash[s[i] - 'a']);
            // 遍历到了最大下标，说明已经包含所有字母
            if (right == i) {
                // 存结果
                result.push_back(right - left + 1);
                // 更新左端点
                left = i + 1;
            }
        }
        return result;
    }
};

题目链接：56. 合并区间

思路

        做的第四道重叠区间的题了，思路大体相同。不重叠时向后遍历，重叠时做处理。这道题的处理稍微有点区别，就是要合并重叠的区间，左端点选最小，右端点选最大，然后继续向后遍历即可。在原数组上修改有些麻烦，直接定义一个新数组存放结果，重叠时pop出来，合并区间后再push进去。

代码

class Solution {
public:
    // 按照左端点从小到大排列
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 只有一个区间时，直接返回
        if (intervals.size() == 1)
            return 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] > intervals[i - 1][1]) {
                result.push_back(intervals[i]);
            } else {
                // 重叠时先把上一个放进去的区间拿出来
                result.pop_back();
                // 合并区间
                intervals[i][0] = min(intervals[i - 1][0], intervals[i][0]);
                intervals[i][1] = max(intervals[i - 1][1], intervals[i][1]);
                // 将合并后的区间存到结果数组
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

总结

        ①重叠区间，一般都要对数组排序，要熟悉sort函数的第三个参数以及排列规则

        ②区间的重叠定义细节要注意，有时两个区间右端点与左端点相等不算重叠，有时算，具体看题目