LeetCode - 区间合并类问题

合并区间

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

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

分析： C++,排序；根据区间左边界排序；如果当前区间的右边界大于等于下一个区间的左边界，则合并；。o(n)的时间复杂度。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if (intervals.empty()) return res;
        sort(intervals.begin(), intervals.end(),
            [ ](vector<int> &v1, vector<int> &v2) { return v1[0] < v2[0];});
        
        for (int i = 0; i < intervals.size(); ++i) {
            vector<int> temp = intervals[i];
            while (i + 1 < intervals.size() && temp[1] >= intervals[i+1][0]) {
                ++i;
                temp[1] = max(temp[1], intervals[i][1]);
            }
            res.push_back(temp);
        }
        return res;
    }
};

插入区间

给出一个无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 。输出: [[1,5],[6,9]]

分析1： 插入后排序，从头到尾遍历合并。

class Solution{
public:
	vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
		vector<vector<int>> res;
		intervals.push_back(newInterval);
		if(newInterval.empty())
			return intervals;
		sort(intervals.begin(), intervals.end(),
			[](vector<int> &v1, vector<int> &v2) { return v1[0] < v2[0]; });

		for (int i = 0; i < intervals.size(); ++i) {
			vector<int> temp = intervals[i];
			while (i + 1 < intervals.size() && temp[1] >= intervals[i + 1][0]) {
				++i;
				temp[1] = max(temp[1], intervals[i][1]);
			}
			res.push_back(temp);
		}
		return res;
	}
};

分析2： 二分找到区间头部该插入的位置，然后向左右扩展合并区间。
右边情况比较复杂，可能会合并好几个区间，左边因为之前二分定位过了，可以肯定最多向左合并一个区间。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int l = 0, r = intervals.size() - 1, mid;
        // 判定特殊情况
        if(r < 0)
        {
            intervals.push_back(newInterval);
            return intervals;
        }
        // 二分查找
        while(l < r)
        {
            mid = (l + r) / 2;
            if(intervals[mid][0] < newInterval[0]) l = mid + 1;
            else r = mid;
        }
        // 判定特殊情况，这里是将区间整个插入到原有区间序列的头或尾
        int x = newInterval[0], y = newInterval[1];
        if(intervals[l][0] > y && (l == 0 || l > 0 && intervals[l - 1][1] < x) || intervals[l][1] < x)
        {
            intervals.push_back({x, y});
            sort(intervals.begin(),intervals.end());
            return intervals;
        }
        // 向右合并
        while(r < intervals.size() && intervals[r][0] <= y)
        {
            y = max(y, intervals[r][1]);
            x = min(x, intervals[r][0]);
            r ++;
        }
        //向左合并
        if(l > 0 && intervals[l - 1][1] >= x)
        {
            x = min(x, intervals[l - 1][0]);
            y = max(y, intervals[l - 1][1]);
            l --;
        }
        // 去除已经合并的区间
        intervals.erase(intervals.begin() + l, intervals.begin() + r);
        intervals.push_back({x, y});
        sort(intervals.begin(),intervals.end());
        return intervals;
    }
};