题目描述
给定一个区间的集合,合并所有重叠的区间,并以 [start, end]
的形式返回合并后的结果。确保合并后的区间列表按非递减顺序排列,且合并后的每个区间的开始值小于或等于前一个区间的结束值。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间,因为它们是连续的。
PHP 示例代码
<?php
function merge($intervals) {
if (empty($intervals)) {
return [];
}
// 根据区间的起始位置进行排序
usort($intervals, function($a, $b) {
return $a[0] - $b[0];
});
$merged = [$intervals[0]]; // 初始化合并后的区间列表
// 遍历排序后的区间,进行合并
for ($i = 1; $i < count($intervals); $i++) {
$current = $intervals[$i];
$lastMerged = $merged[count($merged) - 1];
// 如果当前区间的起始位置小于等于上一个合并区间的结束位置,则进行合并
if ($current[0] <= $lastMerged[1]) {
$lastMerged[1] = max($lastMerged[1], $current[1]); // 更新结束位置
} else {
// 如果不重叠,直接将当前区间加入合并列表
$merged[] = $current;
}
}
return $merged;
}
// 示例用法
$intervals = [[1,3],[2,6],[8,10],[15,18]];
print_r(merge($intervals));
?>
Python 示例代码
def merge(intervals):
if not intervals:
return []
# 根据区间的起始位置进行排序
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
# 遍历排序后的区间,进行合并
for interval in intervals[1:]:
last_merged = merged[-1]
# 如果当前区间的起始位置小于等于上一个合并区间的结束位置,则进行合并
if interval[0] <= last_merged[1]:
last_merged[1] = max(last_merged[1], interval[1])
else:
# 如果不重叠,直接将当前区间加入合并列表
merged.append(interval)
return merged
# 示例用法
intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge(intervals))
JavaScript 示例代码
function merge(intervals) {
if (!intervals.length) {
return [];
}
// 根据区间的起始位置进行排序
intervals.sort((a, b) => a[0] - b[0]);
let merged = [intervals[0]];
// 遍历排序后的区间,进行合并
for (let i = 1; i < intervals.length; i++) {
let current = intervals[i];
let lastMerged = merged[merged.length - 1];
// 如果当前区间的起始位置小于等于上一个合并区间的结束位置,则进行合并
if (current[0] <= lastMerged[1]) {
lastMerged[1] = Math.max(lastMerged[1], current[1]); // 更新结束位置
} else {
// 如果不重叠,直接将当前区间加入合并列表
merged.push(current);
}
}
return merged;
}
// 示例用法
const intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(intervals));
以上代码均展示了如何合并给定区间列表的算法实现,并提供了示例用法。这些代码可以很好地满足面试要求,并可以在码小课网站上作为学习资源分享。