# 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]

### 代码​

// Merge Interval// 复用一下Insert Intervals的解法即可// 时间复杂度O(n1+n2+...)，空间复杂度O(1)public class Solution {    public int[][] merge(int[][] intervals) {        ArrayList<int[]> list = new ArrayList<>();        for (int[] newInterval : intervals) {            insert(list, newInterval);        }        return list.toArray(new int[0][2]);    }    private void insert(ArrayList<int[]> intervals, int[] newInterval) {        for (int i = 0; i < intervals.size();) {            final int[] cur = intervals.get(i);            if (newInterval[1] < cur[0]) {                intervals.add(i, newInterval);                return;            } else if (newInterval[0] > cur[1]) {                ++i;            } else {                newInterval[0] = Math.min(newInterval[0], cur[0]);                newInterval[1] = Math.max(newInterval[1], cur[1]);                intervals.remove(i);            }        }        intervals.add(newInterval);    }}