56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

先对数组进行排序。
遍历数组，当前一个子数组与后一个子数组有重叠时，合并数组。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0],b[0]));

        int i = 0;
        List<int[]> ans = new ArrayList();
        while( i < intervals.length-1 ){
            if(intervals[i][1] >= intervals[i+1][0]){
                intervals[i+1][0] = intervals[i][0];
                intervals[i+1][1] = Math.max(intervals[i][1], intervals[i+1][1]);
                intervals[i] = null;
            }
            i++;
        }
        
        for(int[] interval : intervals){
            if(interval != null){
                ans.add(interval);
            }
        }
        return ans.toArray(new int[ans.size()][2]);
    }
}