输入: [(1,3)]输出: [(1,3)]输入: [(1,3),(2,6),(8,10),(15,18)]输出: [(1,6),(8,10),(15,18)]public class Solution { /** * @param intervals: interval list. * @return: A new interval list. */ public List<Interval> merge(List<Interval> intervals) { if (intervals.size() == 0) { return intervals; } // 根据区间的start值排序 intervals.sort(Comparator.comparing(i -> i.start)); List<Interval> result = new ArrayList<Interval>(); Interval lastInterval = intervals.get(0); // 如果两段区间有交集的话，合并两段区间 // 没有的话，将最后的区间加入答案，并令新的区间作为最后的区间 for (Interval interval: intervals) { if (haveIntercation(lastInterval, interval)) { lastInterval = mergeTwoIntervals(lastInterval, interval); } else { result.add(lastInterval); lastInterval = interval; } } result.add(lastInterval); return result; } // 合并两段区间 private Interval mergeTwoIntervals(Interval a, Interval b) { return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end)); } // 判断区间是否有交集，要满足较大的start小于等于较小的end private boolean haveIntercation(Interval a, Interval b) { return Math.max(a.start, b.start) <= Math.min(a.end, b.end); }}[leetcode/lintcode 题解] Google面试题：合并区间
原文：https://www.cnblogs.com/lintcode/p/13754877.html