Merge Intervals

Question

Problem Statement

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

  1. [                     [
  2.   [1, 3],               [1, 6],
  3.   [2, 6],      =>       [8, 10],
  4.   [8, 10],              [15, 18]
  5.   [15, 18]            ]
  6. ]

Challenge

O(n log n) time and O(1) extra space.

题解1 - 排序后

初次接触这道题可能会先对 interval 排序，随后考虑相邻两个 interval 的 end 和 start 是否交叉，若交叉则合并之。

Java

  1. /**
  2.  * Definition of Interval:
  3.  * public class Interval {
  4.  *     int start, end;
  5.  *     Interval(int start, int end) {
  6.  *         this.start = start;
  7.  *         this.end = end;
  8.  *     }
  9.  */
  11. class Solution {
  12.     /**
  13.      * @param intervals: Sorted interval list.
  14.      * @return: A new sorted interval list.
  15.      */
  16.     public List<Interval> merge(List<Interval> intervals) {
  17.         if (intervals == null || intervals.isEmpty()) return intervals;
  19.         List<Interval> result = new ArrayList<Interval>();
  20.         // sort with Comparator
  21.         Collections.sort(intervals, new IntervalComparator());
  22.         Interval prev = intervals.get(0);
  23.         for (Interval interval : intervals) {
  24.             if (prev.end < interval.start) {
  25.                 result.add(prev);
  26.                 prev = interval;
  27.             } else {
  28.                 prev.start = Math.min(prev.start, interval.start);
  29.                 prev.end = Math.max(prev.end, interval.end);
  30.             }
  31.         }
  32.         result.add(prev);
  34.         return result;
  35.     }
  37.     private class IntervalComparator implements Comparator<Interval> {
  38.         public int compare(Interval a, Interval b) {
  39.             return a.start - b.start;
  40.         }
  41.     }
  43. }

源码分析

这里因为需要比较 interval 的 start, 所以需要自己实现 Comparator 接口并覆盖 compare 方法。这里取 prev 为前一个 interval。最后不要忘记加上 prev.

复杂度分析

排序 O(n \log n), 遍历 O(n), 所以总的时间复杂度为 O(n \log n). 空间复杂度 O(1).

题解2 - 插入排序

除了首先对 intervals 排序外，还可以使用类似插入排序的方法，插入的方法在题 Insert Interval 中已详述。这里将 result 作为 intervals 传进去即可，新插入的 interval 为 intervals 遍历得到的结果。

Java

  1. /**
  2.  * Definition of Interval:
  3.  * public class Interval {
  4.  *     int start, end;
  5.  *     Interval(int start, int end) {
  6.  *         this.start = start;
  7.  *         this.end = end;
  8.  *     }
  9.  */
  11. class Solution {
  12.     /**
  13.      * @param intervals: Sorted interval list.
  14.      * @return: A new sorted interval list.
  15.      */
  16.     public List<Interval> merge(List<Interval> intervals) {
  17.         if (intervals == null || intervals.isEmpty()) return intervals;
  19.         List<Interval> result = new ArrayList<Interval>();
  20.         for (Interval interval : intervals) {
  21.             result = insert(result, interval);
  22.         }
  24.         return result;
  25.     }
  27.     private List<Interval> insert(List<Interval> intervals, Interval newInterval) {
  28.         List<Interval> result = new ArrayList<Interval>();
  29.         int insertPos = 0;
  30.         for (Interval interval : intervals) {
  31.             if (newInterval.end < interval.start) {
  32.                 result.add(interval);
  33.             } else if (newInterval.start > interval.end) {
  34.                 result.add(interval);
  35.                 insertPos++;
  36.             } else {
  37.                 newInterval.start = Math.min(newInterval.start, interval.start);
  38.                 newInterval.end = Math.max(newInterval.end, interval.end);
  39.             }
  40.         }
  41.         result.add(insertPos, newInterval);
  43.         return result;
  44.     }
  45. }

源码分析

关键在 insert 的理解，result = insert(result, interval);作为迭代生成新的 result.

复杂度分析

每次添加新的 interval 都是线性时间复杂度，故总的时间复杂度为 O(1 + 2 + … + n) = O(n^2). 空间复杂度为 O(n).

Reference