Day36重叠区间

By HQWQF 2024/01/21

笔记

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

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

解法

和上一题一样，排序后遍历所有区间，并用上一个区间的右区间判断是否重叠，值得注意的是t代表的是上一个区间的右区间，在两个区间重叠时，我们应该删掉右边界更小的区间来经可能避免重复，对应代码中的t = min(t, intervals[i][1]);

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int t = intervals[0][1];
        int result = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (t > intervals[i][0] ) {  
                result++;
                t = min(t, intervals[i][1]);
            }
            else
            {
                t = intervals[i][1];
            }
        }
        return result;
    }
};

763.划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

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

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

贪心法

统计字符串中所有字母出现的最远位置，然后遍历字符串，不断更新已经遍历到的字母的最远位置，如果这个位置与当前下标相等，说明此后不会出现已经遍历到的字母，说明这里是分割点。将长度放入解集即可。

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] < b[0];
    }
    vector<int> partitionLabels(string s) {
        vector<int> ap(2, -1);
        vector<vector<int>> aps;
        for (int i = 0; i < 26; i++) {
            int first = -1;
            for (int j = 0; j < s.size(); j++) {
                if (s[j] == 'a' + i) {
                    first = j;
                    break;
                }
            }
            int end = -1;
            for (int j = s.size() - 1; j >= 0; j--) {
                if (s[j] == 'a' + i) {
                    end = j;
                    break;
                }
            }
            if (first != -1) {
                vector<int> tmp = {first, end};
                aps.push_back(tmp);
            }
        }
        sort(aps.begin(), aps.end(), cmp);
        int rightBoard = aps[0][1];
        int leftBoard = 0;
        vector<int> result;
        for (int i = 1; i < aps.size(); i++) {
            if (aps[i][0] > rightBoard) {
                result.push_back(rightBoard - leftBoard + 1);
                leftBoard = aps[i][0];
            }
            rightBoard = max(rightBoard, aps[i][1]);
        }
        result.push_back(s.size() - leftBoard);
        return result;
    }
};

和上题类似的做法

直接统计所有字母存在的区间，遍历这些区间，如果区间有交集就当作一个，没有交集就加入解集。

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] < b[0];
    }
    vector<int> partitionLabels(string s) {
        vector<int> ap(2, -1);
        vector<vector<int>> aps;
        for (int i = 0; i < 26; i++) {
            int first = -1;
            for (int j = 0; j < s.size(); j++) {
                if (s[j] == 'a' + i) {
                    first = j;
                    break;
                }
            }
            int end = -1;
            for (int j = s.size() - 1; j >= 0; j--) {
                if (s[j] == 'a' + i) {
                    end = j;
                    break;
                }
            }
            if (first != -1) {
                vector<int> tmp = {first, end};
                aps.push_back(tmp);
            }
        }
        sort(aps.begin(), aps.end(), cmp);
        int rightBoard = aps[0][1];
        int leftBoard = 0;
        vector<int> result;
        for (int i = 1; i < aps.size(); i++) {
            if (aps[i][0] > rightBoard) {
                result.push_back(rightBoard - leftBoard + 1);
                leftBoard = aps[i][0];
            }
            rightBoard = max(rightBoard, aps[i][1]);
        }
        result.push_back(s.size() - leftBoard);
        return result;
    }
};

56.合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

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

解法

这题的不同之处在于需要进行实际的区间合并，我们倾向于添加到解集后，根据后面区间是否重叠选择修改解集的最后一个元素（合并区间）或是将区间添加进解集。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};