56. Merge Intervals
Reference: LeetCode Difficulty: Medium

My Post: [Java] My Sorting Solution (see the 2nd one)

Problem
Given a collection of intervals, merge all overlapping intervals.

Note:

Example:

1 2 3 4 5 Input: [[1 ,3 ],[2 ,6 ],[8 ,10 ],[15 ,18 ]] Output: [[1 ,6 ],[8 ,10 ],[15 ,18 ]] Input: [[1 ,4 ],[4 ,5 ]] Output: [[1 ,5 ]]

Analysis Brute-Force From LeetCode solution section:

The basic idea is to reduce the original problem to a graph problem. Since `[1, 5]`

, `[4, 7]`

, and `[6, 10]`

are overlapping, we construct a connected component of them. After we consider all other intervals, we can have a new interval corresponding to each connected component.

Time: $O(N^2) = O(V + E) = O(V) + O(E) = O(N) + O(N^2)$Space: $O(N^2)$ when all intervals are mutually overlapping.

Sorting The idea is to sort all intervals by starting time. After sorting, we have the following cases to handle

1 2 3 4 5 6 7 8 9 Case 1 : Partially Overlapping --------- ---------- Case 2 : Inclusive Overlapping ------------- -------- Case 3 : Non-Overlapping ------- -------

Here is my original code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 public int [][] merge(int [][] intervals) { int n = intervals.length; if (n == 0 ) return new int [0 ][]; Arrays.sort(intervals, (o1, o2) -> (o1[0 ] - o2[0 ])); List<int []> result = new ArrayList<>(); int [] prev = new int [] { Integer.MIN_VALUE, Integer.MIN_VALUE }; result.add(prev); for (int i = 0 ; i < n; ++i) { int [] curr = intervals[i]; if (prev[1 ] >= curr[0 ] && prev[1 ] <= curr[1 ]) { prev[1 ] = curr[1 ]; } else if (prev[1 ] >= curr[1 ]) { continue ; } else { if (prev[0 ] == Integer.MIN_VALUE && prev[1 ] == Integer.MIN_VALUE) { prev[0 ] = curr[0 ]; prev[1 ] = curr[1 ]; } else { int [] newInterval = new int [] { curr[0 ], curr[1 ] }; result.add(newInterval); prev = newInterval; } } } int [][] ret = new int [result.size()][]; for (int i = 0 ; i < result.size(); ++i) { ret[i] = result.get(i); } return ret; }

I don’t why I made it difficult. We can just set the first interval as `prev`

rather than set it as `Integer.MIN_VALUE`

.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public int [][] merge(int [][] intervals) { int n = intervals.length; if (n == 0 ) { return new int [0 ][]; } Arrays.sort(intervals, (o1, o2) -> (o1[0 ] - o2[0 ])); List<int []> result = new ArrayList<>(); int [] prev = intervals[0 ]; result.add(prev); for (int i = 1 ; i < n; ++i) { int [] curr = intervals[i]; if (prev[1 ] >= curr[0 ] && prev[1 ] <= curr[1 ]) { prev[1 ] = curr[1 ]; } else if (prev[1 ] >= curr[1 ]) { continue ; } else { int [] newInterval = new int [] { curr[0 ], curr[1 ] }; result.add(newInterval); prev = newInterval; } } int [][] ret = new int [result.size()][]; for (int i = 0 ; i < result.size(); ++i) { ret[i] = result.get(i); } return ret; }

Time: $O(N\log{N})$Space: $O(N)$