思路
- 排序：將所有區間按起始點從小到大排序。
- 貪心合并：初始化一個結果列表，放入第一個區間。然后遍歷剩余區間，將當前區間與結果列表中的最后一個區間比較：
- 若重疊（當前區間起點 ≤ 結果區間終點），則更新結果區間的終點為兩者終點的最大值。
- 若不重疊，則將當前區間直接加入結果列表。
C++ 代碼實現
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.size() <= 1) return intervals;sort(intervals.begin(), intervals.end());vector<vector<int>> merged;merged.push_back(intervals[0]);for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] <= merged.back()[1]) {merged.back()[1] = max(merged.back()[1], intervals[i][1]);} else {merged.push_back(intervals[i]);}}return merged;}
};
注：sort 對于 vector<vector<int>> 默認按第一個元素排序，可省略 lambda。
復雜度
- 時間復雜度:
O(n log n)，瓶頸在于排序。 - 空間復雜度:
O(n)，用于存儲返回結果。
