合并区间
题目要求
给定一个区间数组 intervals，其中每个区间表示为形如 [starti, endi] 的子数组。要求编写一个算法，合并所有重叠的区间，并返回一个新的区间数组。新的区间数组中的每个区间应该是不重叠的，并且必须包含输入数组中的所有区间。
解题思路
解决这个问题的关键是要理解何时两个区间可以合并，以及如何合并这些区间。以下是解题的步骤：
-
排序：首先，按照区间的起始位置
starti对所有区间进行排序。这样做的目的是为了让所有可能重叠的区间彼此靠近，便于合并。 -
初始化：创建一个空数组
merged，用于存放合并后的区间。 -
遍历合并：遍历排序后的区间数组
intervals，对于每个区间interval：- 如果
merged为空，或者当前区间的起始位置大于merged中最后一个区间的结束位置，这意味着当前区间与merged中的任何区间都不重叠，可以直接将当前区间添加到merged中。 - 如果当前区间与
merged中最后一个区间重叠（即当前区间的起始位置小于或等于merged中最后一个区间的结束位置），则需要合并这两个区间。合并的方式是更新merged中最后一个区间的结束位置为两个区间结束位置的较大值。
- 如果
-
返回结果：遍历完成后，
merged数组中存放的就是合并后的不重叠区间。返回merged数组作为结果。
通过以上步骤，可以有效地合并所有重叠的区间，并得到一个简洁的不重叠区间数组。
Golang 版本
package main
import (
"fmt"
"sort"
)
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
// 按照区间的起始位置进行排序
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
// 初始化merged数组，添加第一个区间
merged := [][]int{intervals[0]}
// 遍历并合并区间
for i := 1; i < len(intervals); i++ {
last := merged[len(merged)-1] // 获取merged中的最后一个区间
if intervals[i][0] > last[1] {
// 如果当前区间的起始位置大于merged中最后一个区间的结束位置
// 则不重叠，可以直接添加
merged = append(merged, intervals[i])
} else {
// 否则，有重叠，合并区间
last[1] = max(last[1], intervals[i][1])
}
}
return merged
}
// 辅助函数，返回两个整数中较大的一个
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
// 示例
intervals := [][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
mergedIntervals := merge(intervals)
fmt.Println(mergedIntervals) // 输出合并后的区间
}
这段代码定义了一个 merge 函数，它接受一个二维整数数组 intervals 作为参数，返回一个合并后的区间数组。在 main 函数中，我们定义了一个示例区间数组，并调用 merge 函数，然后打印出合并后的结果。
C++版本
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return {};
}
// 按照区间的起始位置排序
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> merged;
merged.push_back(intervals[0]);
// 遍历区间并合并
for (int i = 1; i < intervals.size(); ++i) {
// 如果当前区间的起始位置小于等于merged中最后一个区间的结束位置，则合并
if (intervals[i][0] <= merged.back()[1]) {
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
// 否则，将当前区间添加到merged中
merged.push_back(intervals[i]);
}
}
return merged;
}
};
int main() {
Solution solution;
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> mergedIntervals = solution.merge(intervals);
for (const auto& interval : mergedIntervals) {
cout << "[" << interval[0] << "," << interval[1] << "] ";
}
cout << endl;
return 0;
}
这段 C++代码定义了一个 Solution 类，其中包含了一个 merge 方法，用于合并区间。在 main 函数中，我们创建了一个 Solution 对象，并用一个示例区间数组调用了 merge 方法，最后打印出合并后的区间数组。
Python 版本
def merge(intervals):
if not intervals:
return []
# 按照区间的起始位置排序
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
# 如果当前区间的起始位置小于等于merged中最后一个区间的结束位置，则合并
if current[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], current[1])
else:
# 否则，将当前区间添加到merged中
merged.append(current)
return merged
# 示例
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge(intervals))
这段 Python 代码定义了一个 merge 函数，它接受一个区间列表 intervals 作为参数，并返回合并后的区间列表。在示例中，我们定义了一个区间列表，并调用 merge 函数，然后打印出合并后的结果。
Java 版本
import java.util.Arrays;
import java.util.LinkedList;
public class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) {
return intervals;
}
// 根据区间的起始位置排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
LinkedList<int[]> merged = new LinkedList<>();
for (int[] interval : intervals) {
// 如果列表为空，或者当前区间与列表中最后一个区间不重叠，直接添加
if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
merged.add(interval);
} else {
// 否则，我们合并当前区间与列表中最后一个区间
merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] mergedIntervals = solution.merge(intervals);
for (int[] interval : mergedIntervals) {
System.out.println("[" + interval[0] + "," + interval[1] + "]");
}
}
}
这段 Java 代码定义了一个 Solution 类，其中包含了一个 merge 方法，用于合并区间。在 main 方法中，我们创建了一个 Solution 对象，并用一个示例区间数组调用了 merge 方法，最后打印出合并后的区间数组。
Rust 版本
fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> { if intervals.is_empty() { return vec![]; } // 根据区间的起始位置排序 intervals.sort_by(|a, b| a[0].cmp(&b[0])); let mut merged: Vec<Vec<i32>> = Vec::new(); merged.push(intervals[0].clone()); for i in 1..intervals.len() { let last = merged.last_mut().unwrap(); if intervals[i][0] <= last[1] { last[1] = std::cmp::max(last[1], intervals[i][1]); } else { merged.push(intervals[i].clone()); } } merged } fn main() { let intervals = vec![vec![1, 3], vec![2, 6], vec![8, 10], vec![15, 18]]; let merged_intervals = merge(intervals); for interval in merged_intervals { println!("[{}, {}]", interval[0], interval[1]); } }
这段 Rust 代码定义了一个 merge 函数，它接受一个 Vec<Vec<i32>> 类型的区间列表 intervals 作为参数，并返回合并后的区间列表。在 main 函数中，我们定义了一个区间列表，并调用 merge 函数，然后打印出合并后的结果。
总结
合并区间的问题可以通过以下步骤解决：
-
排序：首先，根据每个区间的起始位置对区间列表进行排序。这是为了让所有可能需要合并的区间排列在一起，便于后续处理。
-
初始化：创建一个新的区间列表（在 Rust 中是
Vec<Vec<i32>>，在 Java 中是LinkedList<int[]>，在 C++中是vector<vector<int>>，在 Python 中是列表），并将排序后的第一个区间添加到这个列表中。这个列表将用于存储最终合并后的区间。 -
遍历与合并：遍历排序后的区间列表，对于每个区间：
- 如果当前区间的起始位置小于或等于新区间列表中最后一个区间的结束位置，则说明这两个区间有重叠，需要合并。合并操作是将新区间列表中最后一个区间的结束位置更新为当前区间和最后一个区间结束位置的较大值。
- 如果当前区间的起始位置大于新区间列表中最后一个区间的结束位置，则说明这两个区间没有重叠，可以直接将当前区间添加到新区间列表中。
-
返回结果：遍历完成后，新区间列表中存储的就是合并后的区间。返回这个列表作为结果。
在不同的编程语言中，具体的语法和数据结构有所不同，但算法的核心思想是一致的。例如，在 Rust 中使用Vec和sort_by方法进行排序，在 Java 中使用LinkedList和Arrays.sort方法，在 C++中使用vector和sort函数，在 Python 中使用列表和sort方法。