LeetCode 56. Merge Intervals

Problem

LeetCode 56. Merge Intervals

1. 题目简述

给出一系列区间，合并它们，给出合并后的结果。例如：

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

2. 算法思路

相关问题：

1. LeetCode 57. Insert Interval
2. LeetCode 253. Meeting Rooms II（待做，会议室问题的一系列，很重要）

也算是老经典的区间相关的问题了，可以单独整理一个小专题。慢慢添加，其实和57题基本上是一致的，都是先按照左边界进行排序，然后对右边界进行处理。

暴力做法

其实最大的问题就是如何合并两个相邻区间，每次先取一个区间，然后和后面的进行合并，直到不能够再合并为止。不能再合并的条件就是后一个的start大于前一个的end，然后先用一个List存着，然后再转为Array，注意List转为Array的方法！！！

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][0];
        }

        List<int[]> merged = new ArrayList();

        // 首先对区间进行排序
        Arrays.sort(intervals, (int[] a, int[] b) -> {
            return a[0] - b[0];
        });

        for (int i = 0; i < intervals.length; i++) {
            int[] temp = intervals[i];

            // 依次合并后面的可以合并的interval，经过排序后保证了后面的start一定是不小于当前的start的，因此只要判断后者的start和当前的end的大小
            while (i + 1 < intervals.length && intervals[i + 1][0] <= temp[1]) {
                temp[1] = Math.max(intervals[i + 1][1], temp[1]);
                i++;
            }

            merged.add(temp);
        }

        return merged.toArray(new int[merged.size()][2]);
    }
}