Merge Intervals

LeetCode Q 56 - Merge Intervals

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.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

Code:

public int[][] merge(int[][] intervals) {
	
	if (intervals == null || intervals.length <= 1) return intervals;

	Arrays.sort(intervals, (a, b) -> {
		if (a[0] != b[0])
			return a[0] - b[0];
		return a[1] - b[1];
	});

	List<int[]> list = new ArrayList<>();
	list.add(intervals[0]);

	for (int i = 1; i < intervals.length; i++) {
		int[] prev = list.get(list.size() - 1);
		if (prev[1] < intervals[i][0])
			list.add(intervals[i]);
		else 
			prev[1] = Math.max(prev[1], intervals[i][1]);
	} 

	int[][] res = new int[intervals.length][2];
	int index = 0;

	for (int[] arr: list)
		res[index++] = arr;

	return res;
}