題目
以數組 intervals 表示若干個區間的集合，其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間，并返回 一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間 。
示例
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
思路
合并重疊區間的一種常見思路是通過排序和遍歷來實現：
-
首先，將給定的區間集合按照區間的起始位置進行排序。這樣做的目的是為了方便后續的合并操作。
-
初始化一個空的結果集，用于存儲合并后的區間。
-
遍歷排序后的區間集合。對于每個區間，分為兩種情況進行處理：
-
如果當前結果集為空，或者當前區間與結果集中最后一個區間無重疊（即當前區間的起始位置大于結果集中最后一個區間的結束位置），則將當前區間直接加入結果集。
-
否則，說明當前區間與結果集中最后一個區間存在重疊。此時，更新結果集中最后一個區間的結束位置，使其變為當前區間的結束位置和原始結束位置中的較大值。
-
-
遍歷結束后，得到的結果集即為合并后的不重疊區間數組。
這種方法的時間復雜度主要取決于排序的時間復雜度，通常為 O(nlogn)，其中 n 是區間的個數。遍歷區間的時間復雜度為 O(n)。因此，整體的時間復雜度為 O(nlogn)。
Code：
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 首先按照區間起始位置進行排序sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];});vector<vector<int>> result;for (const vector<int>& interval : intervals) {// 如果當前結果集為空，或者當前區間與結果集中最后一個區間無重疊，則將當前區間加入結果集if (result.empty() || interval[0] > result.back()[1]) {result.push_back(interval);} else {// 否則，更新結果集中最后一個區間的結束位置result.back()[1] = max(result.back()[1], interval[1]);}}return result;}
};
)
