56. Merge Intervals (1)

Link

Given a collection of intervals, merge all overlapping intervals.

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

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        
        if(intervals.length <= 1){
            return intervals;
        }
        
        //need to sort before checking, otherwise will misjudge the ovelap case
        //ex: {[1,4][0,0]} -> misjude the [0,0] is overlapped with [1,4]
        Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));
        
        int newStart = intervals[0][0];
        int newEnd = intervals[0][1];
        
        for(int i = 1; i < intervals.length; i++){
            int curStart = intervals[i][0];
            int curEnd = intervals[i][1];
            //no overlap
            if(curStart > newEnd){
                list.add(new int[]{newStart, newEnd});
                newStart = curStart;
                newEnd = curEnd;
            }
            else{
                newStart = Math.min(newStart, curStart);
                newEnd = Math.max(newEnd, curEnd);
            }
        }
        list.add(new int[]{newStart, newEnd});
        
        return list.toArray(new int[list.size()][2]);
    }
}