56.合并区间

题目描述

给出一个区间的集合，请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

问题分析

• 可以通过第一个元素排序，结合首尾信息进行判断区间
  首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；

否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

• 双指针方法
  1.对 vector<vector<int>> 排序，需要按照先比较区间开始，如果相同再比较区间结束，使用默认的排序规则即可
  2.使用双指针，左边指针指向当前区间的开始
  3.使用一个变量来记录连续的范围 t
  4.右指针开始往后寻找，如果后续的区间的开始值比 t 还小，说明重复了，可以归并到一起
  5.此时更新更大的结束值到 t
  6.直到区间断开，将 t 作为区间结束，存储到答案里
  7.然后移动左指针，跳过中间已经合并的区间

解题方法1

• 排序法

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0)
        {
            return{};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> mergeV;
        for (int i = 0; i < intervals.size(); ++i)
        {
            int L = intervals[i][0], R = intervals[i][1];

            if (!mergeV.size() || L > mergeV.back()[1])
            {
                mergeV.push_back({ L,R });
            }
            else
            {
                mergeV.back()[1] = max(R, mergeV.back()[1]);
            }
        }
        return mergeV;
    }
};

解题思路2

• 双指针法

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