共计 1248 个字符，预计需要花费 4 分钟才能阅读完成。
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
难度：medium
题目：给定间隔点集合，合并所有重复的间隔。
思路：先排序然后合并。
Runtime: 57 ms, faster than 21.60% of Java online submissions for Merge Intervals.Memory Usage: 35 MB, less than 3.23% of Java online submissions for Merge Intervals.
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0;}
* Interval(int s, int e) {start = s; end = e;}
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (null == intervals || intervals.isEmpty()) {
return new ArrayList<>();
}
Collections.sort(intervals, (o1, o2) -> {
Interval i1 = (Interval) o1;
Interval i2 = (Interval) o2;
if (0 == Integer.compare(i1.start, i2.start)) {
return Integer.compare(i1.end, i2.end);
}
return Integer.compare(i1.start, i2.start);
});
Stack<Interval> stack = new Stack<>();
stack.push(intervals.get(0));
for (int i = 1; i < intervals.size(); i++) {
Interval i1 = stack.pop();
Interval i2 = intervals.get(i);
if (i1.end >= i2.start) {
stack.push(new Interval(i1.start, Math.max(i1.end, i2.end)));
} else {
stack.push(i1);
stack.push(i2);
}
}
return new ArrayList<>(stack);
}
}
