題目描述

給出一個(gè)區(qū)間的集合，請(qǐng)合并所有重疊的區(qū)間。
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

問題分析

• 可以通過第一個(gè)元素排序税娜，結(jié)合首尾信息進(jìn)行判斷區(qū)間
  首先，我們將列表中的區(qū)間按照左端點(diǎn)升序排序簸淀。然后我們將第一個(gè)區(qū)間加入 merged 數(shù)組中晒喷，并按順序依次考慮之后的每個(gè)區(qū)間：

如果當(dāng)前區(qū)間的左端點(diǎn)在數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)之后，那么它們不會(huì)重合映皆，我們可以直接將這個(gè)區(qū)間加入數(shù)組 merged 的末尾挤聘；

否則，它們重合捅彻，我們需要用當(dāng)前區(qū)間的右端點(diǎn)更新數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)组去，將其置為二者的較大值。

• 雙指針方法
  1.對(duì) vector<vector<int>> 排序步淹，需要按照先比較區(qū)間開始从隆，如果相同再比較區(qū)間結(jié)束诚撵，使用默認(rèn)的排序規(guī)則即可
  2.使用雙指針，左邊指針指向當(dāng)前區(qū)間的開始
  3.使用一個(gè)變量來記錄連續(xù)的范圍 t
  4.右指針開始往后尋找键闺，如果后續(xù)的區(qū)間的開始值比 t 還小寿烟，說明重復(fù)了，可以歸并到一起
  5.此時(shí)更新更大的結(jié)束值到 t
  6.直到區(qū)間斷開辛燥，將 t 作為區(qū)間結(jié)束韧衣，存儲(chǔ)到答案里
  7.然后移動(dòng)左指針，跳過中間已經(jīng)合并的區(qū)間

解題方法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;
    }
};