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][];
  // Sort
  Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0])); // by starting time
  // Init
  List<int[]> result = new ArrayList<>();
  int[] prev = new int[] { Integer.MIN_VALUE, Integer.MIN_VALUE }; // prev points to the current interval in result list
  result.add(prev);
  // Go through each interval
  for (int i = 0; i < n; ++i) {
    int[] curr = intervals[i];
    if (prev[1] >= curr[0] && prev[1] <= curr[1]) {
      // partially overlapped
      prev[1] = curr[1]; // just modify existing prev
    } else if (prev[1] >= curr[1]) {
      // prev contains curr
      continue;
    } else { // do not overlapped
      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; 
      }
    }
  }
  // Convert to int[][]
  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][];
  }
  // Sort
  Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0])); // by starting time
  // Init
  List<int[]> result = new ArrayList<>();
  int[] prev = intervals[0]; // requires 0-size check
  result.add(prev);
  // Go through each interval (skip the first interval)
  for (int i = 1; i < n; ++i) {
    int[] curr = intervals[i];
    if (prev[1] >= curr[0] && prev[1] <= curr[1]) {
      // partially overlapped
      prev[1] = curr[1]; // just modify existing prev -> combine
    } else if (prev[1] >= curr[1]) {
      // prev contains curr (inclusive) -> ignore curr
      continue;
    } else { // do not overlapped
      int[] newInterval = new int[] { curr[0], curr[1] };
      result.add(newInterval);
      prev = newInterval;
    }
  }
  // Convert to int[][]
  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)$