Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3
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:

1
2
3
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.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
		List<int[]> result = new ArrayList<>();
		for (int[] curr : intervals) {
			if (result.isEmpty()) {
				result.add(curr);
				continue;
			}
			int[] prev = result.get(result.size() - 1);
			if (prev[1] < curr[0]) {
				result.add(curr);
			} else {
				prev[1] = Math.max(curr[1], prev[1]);
			}
		}
		return result.toArray(new int[0][0]);
	}
}