Merge Intervals

描述

Given a collection of intervals, merge all overlapping intervals.

For example,Given [1,3],[2,6],[8,10],[15,18],return [1,6],[8,10],[15,18]

分析

复用一下Insert Intervals的解法即可，创建一个新的interval集合，然后每次从旧的里面取一个interval出来，然后插入到新的集合中。

代码

  1. // Merge Interval
  2. //复用一下Insert Intervals的解法即可
  3. // 时间复杂度O(n1+n2+...)，空间复杂度O(1)
  4. public class Solution {
  5.     public List<Interval> merge(List<Interval> intervals) {
  6.         List<Interval> result = new ArrayList<>();
  7.         for (int i = 0; i < intervals.size(); i++) {
  8.             insert(result, intervals.get(i));
  9.         }
  10.         return result;
  11.     }
  12.     private static List<Interval> insert(List<Interval> intervals,
  13.                                          Interval newInterval) {
  14.         for (int i = 0; i < intervals.size();) {
  15.             final Interval cur = intervals.get(i);
  16.             if (newInterval.end < cur.start) {
  17.                 intervals.add(i, newInterval);
  18.                 return intervals;
  19.             } else if (newInterval.start > cur.end) {
  20.                 ++i;
  21.                 continue;
  22.             } else {
  23.                 newInterval.start = Math.min(newInterval.start, cur.start);
  24.                 newInterval.end = Math.max(newInterval.end, cur.end);
  25.                 intervals.remove(i);
  26.             }
  27.         }
  28.         intervals.add(newInterval);
  29.         return intervals;
  30.     }
  31. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/merge-intervals.html