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)$


Comment