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.

class Solution {
    public int[][] merge(int[][] intervals) {
        
    }
}

Problem Clarification

[1, 4] and [4, 5] overlap, thus if even ends meet, we need to merge them.

Idea - 1

For two intervals [a1, b1] and [a2, b2] if we have a1 ≤ a2 then they overlap if b1 ≥ a2. One the other hand, if b1 < a2, then [a1, b1] does not overlap with [a2, b2] or with any interval [ai, bi] where b1 < ai. In that case we can output [a1, b1] and move on. Thus sorting helps. The resulting algorithm has time and space .

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if(n < 2)
        {
            return intervals;
        }
        
        Arrays.sort( intervals, new Comparator<int[]>()
                    {
                        public int compare(int[] a, int[] b)
                        {
                            return a[0]-b[0];
                        }
                    });
        
        List<int[]> tmp = new ArrayList<>();
        int[] prev = intervals[0];
        for(int i = 1; i < n; ++i)
        {
            int[] curr = intervals[i];
            if(prev[1] >= curr[0]) // overlaps
            {
                prev[0] = Math.min(prev[0], curr[0]);
                prev[1] = Math.max(prev[1], curr[1]);
            }
            else
            {
                tmp.add(prev);
                prev = curr;
            }
        }
        
        tmp.add(prev);
        
        int[][] result = new int[tmp.size()][2];
        for(int i = 0; i < tmp.size(); ++i)
        {
            result[i] = tmp.get(i);
        }
        
        return result;
    }
}


Runtime: 6 ms, faster than 96.10% of Java online submissions for Merge Intervals.
Memory Usage: 43.9 MB, less than 61.07% of Java online submissions for Merge Intervals.