#P4012. 合并区间
-
ID: 2219
Tried: 601
Accepted: 230
Difficulty: 5
合并区间
题目内容
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i]=[starti,endi] 。请你合并所有重叠的区间，并输出一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
输入描述
第一行为一个整数 n ，代表数组 intervals的长度。 接下来的n行，每行有两个整数starti,endi，代表第i个区间。
输出描述
如题，每行输出一个区间，区间的数字以空额分隔。每个区间以starti升序输出。
样例1
输入
4
1 3
2 6
8 10
15 18
输出
1 6
8 10
15 18
说明
区间 [1,3]和[2,6]重叠, 将它们合并为[1,6]
样例2
输入
2
1 4
4 5
输出
1 5
说明
区间[1,4]和 [4,5] 可被视为重叠区间。
提示
- 1<=intervals.length<=104
- intervals[i].length==2
- 0<=starti<=endi<=104
合并区间问题
题解思路
本题的核心在于区间合并，首先要对区间进行排序，然后通过遍历并合并相邻区间的方式来消除重叠的部分。
具体步骤如下：
- 排序：首先按照区间的起点
start进行升序排序，如果start相同，则按照end排序（默认即可）。 - 合并区间：
- 使用一个
merged列表存储合并后的区间。 - 遍历排序后的区间：
- 如果
merged为空，或者当前区间的start大于merged最后一个区间的end，说明它们不重叠，直接加入merged。 - 否则，说明有重叠，合并方式是：更新
merged最后一个区间的end为max(当前区间的end, merged最后一个区间的end)。
- 如果
- 使用一个
复杂度分析
- 排序：时间复杂度为 O(n log n)。
- 遍历合并：一次遍历，时间复杂度为 O(n)。
- 总复杂度：主要由排序决定，即 O(n log n)。
代码实现
Python 实现
class Solution:
def merge(self, intervals):
if not intervals:
return []
# 1. 先按照区间的起点排序
intervals.sort()
merged = []
for interval in intervals:
# 2. 如果结果数组为空，或者当前区间与前一个区间不重叠，直接加入
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# 3. 否则有重叠，更新 merged 最后一个区间的右边界
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
if __name__ == "__main__":
n = int(input()) # 读取区间数量
intervals = [list(map(int, input().split())) for _ in range(n)] # 读取所有区间
solution = Solution()
result = solution.merge(intervals)
for start, end in result:
print(start, end)
Java 实现
import java.util.*;
public class Main {
public class Solution {
public List<int[]> merge(int[][] intervals) {
List<int[]> merged = new ArrayList<>();
if (intervals.length == 0) return merged;
// 1. 先按照区间的起点进行排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
for (int[] interval : intervals) {
// 2. 如果结果数组为空，或者当前区间与前一个区间不重叠，直接加入
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
merged.add(interval);
} else {
// 3. 否则有重叠，更新 merged 最后一个区间的右边界
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
}
}
return merged;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取区间数量
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = scanner.nextInt();
intervals[i][1] = scanner.nextInt();
}
scanner.close();
Main main = new Main();
Solution solution = main.new Solution();
List<int[]> result = solution.merge(intervals);
for (int[] interval : result) {
System.out.println(interval[0] + " " + interval[1]);
}
}
}
C++ 实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> merged;
if (intervals.empty()) return merged;
// 1. 按照区间的起点排序
sort(intervals.begin(), intervals.end());
for (auto& interval : intervals) {
// 2. 如果 merged 为空或者当前区间与前一个区间不重叠，直接加入
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
// 3. 否则有重叠，更新 merged 最后一个区间的右边界
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
};
int main() {
int n;
cin >> n; // 读取区间数量
vector<vector<int>> intervals(n, vector<int>(2));
for (int i = 0; i < n; i++) {
cin >> intervals[i][0] >> intervals[i][1];
}
Solution solution;
vector<vector<int>> result = solution.merge(intervals);
for (auto& interval : result) {
cout << interval[0] << " " << interval[1] << endl;
}
return 0;
}