56. Merge Intervals
給定一個區間數組，其中 intervals[i] = [starti, endi]，合併所有重疊的區間，並返回一個不重疊的區間數組，該數組覆蓋了輸入中的所有區間。
範例 1：
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出：[[1,6],[8,10],[15,18]] 解釋：由於區間 [1,3] 和 [2,6] 重疊，將它們合併為 [1,6]。
Python
from typing import List
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
# Sort the intervals based on the starting times
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# If the list of merged intervals is empty or the
current interval does not overlap with the previous one
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# There is overlap, so we merge the current interval with
the previous one
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
20.58MB, 129ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// Sort the intervals based on the starting times
sort(intervals.begin(), intervals.end(), [](const vector<int>& a,
const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> merged;
for (const auto& interval : intervals) {
// If the list of merged intervals is empty or the current interval
does not overlap with the previous one
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
// There is overlap, so we merge the current interval with the
previous one
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
};
22.69MB, 19ms
Javascript
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
if (intervals.length === 0) {
return [];
}
// Sort the intervals based on the starting times
intervals.sort((a, b) => a[0] - b[0]);
const merged = [];
for (let interval of intervals) {
// If the list of merged intervals is empty or the current interval does
not overlap with the previous one
if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
merged.push(interval);
} else {
// There is overlap, so we merge the current interval with the previous
one
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1],
interval[1]);
}
}
return merged;
};
57.79MB, 92ms
