1. 原题链接
https://leetcode.com/problems/merge-intervals/description/
2. 题目要求
给定一个Interval对象集合，然后对重叠的区域进行合并。Interval定义如下
例如下图中，[1, 3] 和 [2, 6]是有重叠部分的，可以合并成[1, 6]
3. 解题思路
先取第一个interval对象的 start 和 end 的值 ，然后对这个集合进行遍历。比较当前遍历对象的start是否比前一个对象的end小，小的话则说明二者存在覆盖，然后对二者进行合并
4. 代码实现
import java.util.LinkedList;
import java.util.List; public class MergeIntervals56 {
public static void main(String[] args) {
Interval in1 = new Interval(1, 3);
Interval in2 = new Interval(2, 6);
Interval in3 = new Interval(8, 10);
Interval in4 = new Interval(15, 18);
List<Interval> ls = new LinkedList<Interval>();
ls.add(in1);
ls.add(in2);
ls.add(in3);
ls.add(in4);
for (Interval in : merge(ls))
System.out.println(in.start + " " + in.end);
} public static List<Interval> merge(List<Interval> intervals) {
if (intervals.size() <= 1)
return intervals;
List<Interval> res = new LinkedList<Interval>();
intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval in : intervals) {
if (in.start <= end) {
end = Math.max(in.end, end);
} else {
res.add(new Interval(start, end));
start = in.start;
end = in.end;
}
}
res.add(new Interval(start, end));
return res;
}
} class Interval {
int start;
int end; Interval() {
start = 0;
end = 0;
} Interval(int s, int e) {
start = s;
end = e;
}
}