56. Merge Intervals

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); }}