Problem
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.
Solution
If the arrays is sorted by the first elements, then we can scan through the arrays. For the current array, if the left boundary is within the previous array's range, we merge the current array with the previous array, otherwise we add the previous array to solution set, then replace the previous array with the current array. The cost will be O(N) and space is O(1). If we need to sort the arrays, the cost will be O(NlogN).
import java.util.*;
public class MergeIntervals {
private static class ArrayComparator implements Comparator<int[]> {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
}
public static List<int[]> intervalsMerge(int[][] arrs) {
Collections.sort(Arrays.asList(arrs), new ArrayComparator());
//{1,3},{2,6},{8,10},{15,18}
int[] pre = arrs[0]; //15 18
List<int[]> result = new ArrayList<>(); //1, 6; 1 10;
for(int i = 1; i < arrs.length; i++) {
int[] cur = arrs[i]; //15 18
if(pre[1] < cur[0]) { //
result.add(pre);
pre = cur;
} else {
pre[1] = cur[1]; //
}
}
result.add(pre);
return result;
}
public static void main(String...args) {
int[][] arrs = new int[][] {
{1,3},{2,6},{8,10},{15,18}
};
for(int[] arr : intervalsMerge(arrs)) {
System.out.println("[" + arr[0] + " " + arr[1] + "]");
}
}
}
public class MergeIntervals {
private static class ArrayComparator implements Comparator<int[]> {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
}
public static List<int[]> intervalsMerge(int[][] arrs) {
Collections.sort(Arrays.asList(arrs), new ArrayComparator());
//{1,3},{2,6},{8,10},{15,18}
int[] pre = arrs[0]; //15 18
List<int[]> result = new ArrayList<>(); //1, 6; 1 10;
for(int i = 1; i < arrs.length; i++) {
int[] cur = arrs[i]; //15 18
if(pre[1] < cur[0]) { //
result.add(pre);
pre = cur;
} else {
pre[1] = cur[1]; //
}
}
result.add(pre);
return result;
}
public static void main(String...args) {
int[][] arrs = new int[][] {
{1,3},{2,6},{8,10},{15,18}
};
for(int[] arr : intervalsMerge(arrs)) {
System.out.println("[" + arr[0] + " " + arr[1] + "]");
}
}
}
Time cost O(NlogN), space cost O(1)
Another approach is similar to Meeting Rooms II. We can sort all the start and end points. Then we iterate them, whenever count is 0, we add a range to the result -- we got an end point also register a new start point. A previous registered start point and current end point form a range to be added to the result.
