class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
}
};
56. 合并区间
以数组 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].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104原站题解
php 解法, 执行用时: 48 ms, 内存消耗: 32 MB, 提交时间: 2023-08-27 10:09:15
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer[][]
*/
function merge($intervals) {
usort($intervals, function ($a, $b) {
return $a[0] - $b[0];
});
$ans = [];
foreach ($intervals as $interval) {
if (isset($ans[count($ans) - 1]) && $interval[0] <= $ans[count($ans) - 1][1]) {
$ans[count($ans) - 1][1] = max($ans[count($ans) - 1][1], $interval[1]);
} else {
$ans[] = $interval;
}
}
return $ans;
}
}
typescript 解法, 执行用时: 100 ms, 内存消耗: 48 MB, 提交时间: 2023-08-27 10:04:43
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const ans: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; ++i) {
if (ans.at(-1)[1] < intervals[i][0]) {
ans.push(intervals[i]);
} else {
ans.at(-1)[1] = Math.max(ans.at(-1)[1], intervals[i][1]);
}
}
return ans;
}
golang 解法, 执行用时: 12 ms, 内存消耗: 6.6 MB, 提交时间: 2023-08-27 10:04:23
func merge(intervals [][]int) (ans [][]int) {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
ans = append(ans, intervals[0])
for _, e := range intervals[1:] {
if ans[len(ans)-1][1] < e[0] {
ans = append(ans, e)
} else {
ans[len(ans)-1][1] = max(ans[len(ans)-1][1], e[1])
}
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
java 解法, 执行用时: 7 ms, 内存消耗: 44.5 MB, 提交时间: 2023-08-27 10:03:57
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
List<int[]> merged = new ArrayList<int[]>();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 17.9 MB, 提交时间: 2022-08-26 15:48:35
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
ans = []
intervals.sort(key=lambda x: x[0])
for interval in intervals:
# 如果列表为空，或者当前区间与上一区间不重合，直接添加
if not ans or ans[-1][1] < interval[0]:
ans.append(interval)
else:
ans[-1][1] = max(ans[-1][1], interval[1])
return ans