56. Merge Intervals

思路

首先要注意的是，所给的 interval 数组是无序的。解法一要先将数组按左边界大小排序。新建一个空 List 存储所有 merge 后的 intervals。然后遍历排序好的数组，如果其中的 interval 和 list 中最后一个 interval 有重合区域，将 list 中的这个 interval 扩展。如果包含在内，则不发生变化。如果没有重合区域，就将这个新的 interval 添加进 list 中。

解法一

/*
Sort the intervals according to their start value;
Initialize a list newInterval to store result intervals;
Set the first value of the list to be the first element newInterval in the sorted interval array.
for (intervals[0], intervals[1], ... ,intervals[n - 1])
    // If overlap, set the larger end to be the end for newInterval;
    if (intervals[i][0] >= newInterval[0])
        end of last result interval = max(intervals[i][1], newInterval[1]);
    else
        newInterval = intervals[i];
        add(newInterval);
    endif
    return the result interval;
*/
class Solution {
    public int[][] merge(int[][] intervals) {
        // return the original array if its length <= 1
        if (intervals.length <= 1) {
            return intervals;
        }
        Arrays.sort(intervals,(i1, i2)->Integer.compare(i1[0], i2[0])); // O(nlogn)
        List<int[]> result = new ArrayList<>();
        int[] newInterval = intervals[0];
        result.add(newInterval);
        for (int[] interval : intervals) {
            // Overlap
            if (interval[0] <= newInterval[1]) {
                // Update the end of the last interval in the result
                result.get(result.size() - 1)[1] = Math.max(interval[1], newInterval[1]);
            }
            // Not overlap, just add the interval to the result.
            else {
                newInterval = interval;
                result.add(newInterval);
            }
        }
        return result.toArray(new int[result.size()][2]);
    }
}