# Merge Intervals ### Source - leetcode: [Merge Intervals | LeetCode OJ](https://leetcode.com/problems/merge-intervals/) - lintcode: [(156) Merge Intervals](http://www.lintcode.com/en/problem/merge-intervals/) ### Problem Given a collection of intervals, merge all overlapping intervals. #### Example Given intervals => merged intervals: ~~~ [ [ [1, 3], [1, 6], [2, 6], => [8, 10], [8, 10], [15, 18] [15, 18] ] ] ~~~ #### Challenge O(n log n) time and O(1) extra space. ### 題解1 - 排序后 初次接觸這道題可能會先對 interval 排序，隨后考慮相鄰兩個 interval 的 end 和 start 是否交叉，若交叉則合并之。 ### Java ~~~ /** * Definition of Interval: * public class Interval { * int start, end; * Interval(int start, int end) { * this.start = start; * this.end = end; * } */ class Solution { /** * @param intervals: Sorted interval list. * @return: A new sorted interval list. */ public List<Interval> merge(List<Interval> intervals) { if (intervals == null || intervals.isEmpty()) return intervals; List<Interval> result = new ArrayList<Interval>(); // sort with Comparator Collections.sort(intervals, new IntervalComparator()); Interval prev = intervals.get(0); for (Interval interval : intervals) { if (prev.end < interval.start) { result.add(prev); prev = interval; } else { prev.start = Math.min(prev.start, interval.start); prev.end = Math.max(prev.end, interval.end); } } result.add(prev); return result; } private class IntervalComparator implements Comparator<Interval> { public int compare(Interval a, Interval b) { return a.start - b.start; } } } ~~~ ### 源碼分析 這里因為需要比較 interval 的 start, 所以需要自己實現 Comparator 接口并覆蓋 compare 方法。這里取 prev 為前一個 interval。最后不要忘記加上 prev. ### 復雜度分析 排序 O(nlogn)O(n \log n)O(nlogn), 遍歷 O(n)O(n)O(n), 所以總的時間復雜度為 O(nlogn)O(n \log n)O(nlogn). 空間復雜度 O(1)O(1)O(1). ### 題解2 - 插入排序 除了首先對 intervals 排序外，還可以使用類似插入排序的方法，插入的方法在題 [Insert Interval ](http://algorithm.yuanbin.me/zh-cn/problem_misc/insert_interval.html) 中已詳述。這里將 result 作為 intervals 傳進去即可，新插入的 interval 為 intervals 遍歷得到的結果。 ### Java ~~~ /** * Definition of Interval: * public class Interval { * int start, end; * Interval(int start, int end) { * this.start = start; * this.end = end; * } */ class Solution { /** * @param intervals: Sorted interval list. * @return: A new sorted interval list. */ public List<Interval> merge(List<Interval> intervals) { if (intervals == null || intervals.isEmpty()) return intervals; List<Interval> result = new ArrayList<Interval>(); for (Interval interval : intervals) { result = insert(result, interval); } return result; } private List<Interval> insert(List<Interval> intervals, Interval newInterval) { List<Interval> result = new ArrayList<Interval>(); int insertPos = 0; for (Interval interval : intervals) { if (newInterval.end < interval.start) { result.add(interval); } else if (newInterval.start > interval.end) { result.add(interval); insertPos++; } else { newInterval.start = Math.min(newInterval.start, interval.start); newInterval.end = Math.max(newInterval.end, interval.end); } } result.add(insertPos, newInterval); return result; } } ~~~ ### 源碼分析 關鍵在 insert 的理解，`result = insert(result, interval);`作為迭代生成新的 result. ### 復雜度分析 每次添加新的 interval 都是線性時間復雜度，故總的時間復雜度為 O(1+2+...+n)=O(n2)O(1 + 2 + ... + n) = O(n^2)O(1+2+...+n)=O(n2). 空間復雜度為 O(n)O(n)O(n). ### Reference - [Merge Intervals 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/merge-intervals/) - Soulmachine 的 leetcode 題解