作者：邹昕明 | 来源：互联网 | 2023-10-10 10:35
给定一组区间，将所有区间重叠的部分合并起来。e.g. 给出{[1,3],[2,6],[8,10],[15,18]}，返回{[1,6],[8,10],[15,18]} 区间使用结构体
给定一组区间，将所有区间重叠的部分合并起来。
e.g.
给出 { [1, 3], [2, 6], [8, 10], [15, 18] }，
返回 { [1, 6], [8, 10], [15, 18] }
区间使用结构体（C++）或类（Java）表示
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
原理很简单，按区间的第一个元素 start 递增的顺序排序所有区间，如果一个区间的 end 大于等于 后面一个区间的 start，说明两区间有重叠部分可以合并。
问题的难点就在于如何排序区间，C++ 11 和 Java 8 都引入了 lambda 函数（匿名函数）与 sort 结合来自定义排序方式。
C++实现：
1 vector merge(vector& intervals) {
2 if (intervals.empty()) return {};
3 sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b){ return a.start < b.start; });
4 vector result;
5 result.push_back(intervals[0]);
6 for (int i = 1; i ) {
7 if (result.back().end < intervals[i].start) {
8 result.push_back(intervals[i]);
9 } else {
10 result.back().end = max(result.back().end, intervals[i].end);
11 }
12 }
13 return result;
14 }
Java实现：
1 public List merge(List intervals) {
2 if (intervals.isEmpty()) return new LinkedList();
3 intervals.sort((a, b) -> Integer.compare(a.start, b.start));
4 List result = new LinkedList();
5 result.add(intervals.get(0));
6 for (int i = 1; i ) {
7 if (result.get(result.size() - 1).end < intervals.get(i).start) {
8 result.add(intervals.get(i));
9 } else {
10 result.get(result.size() - 1).end = Math.max(result.get(result.size() - 1).end, intervals.get(i).end);
11 }
12 }
13 return result;
14 }
京公网安备 11010802041100号