Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

To merge overlapping intervals efficiently, we can follow a systematic approach. The idea is to first sort the intervals by their starting points and then merge any overlapping intervals. Let’s break down the process and enhance the explanation with examples.

Step-by-Step Approach

1. Sort the Intervals: First, we sort the list of intervals based on their starting points. This allows us to easily find overlapping intervals.
2. Merge Overlapping Intervals: We take the first interval and compare its end with the start of the next interval. If they overlap (i.e., if the start of the next interval is less than or equal to the end of the current interval), we update the end of the current interval to be the maximum end of the overlapping intervals.
3. Add to Result and Start Over: Once we find an interval that does not overlap, we add the merged interval to our result list and start the process again with the next interval.

Example

Let’s consider the following intervals:

[(1, 3), (2, 6), (8, 10), (15, 18)]

Step 1: Sorting the Intervals

After sorting, these intervals remain the same:

[(1, 3), (2, 6), (8, 10), (15, 18)]

Step 2: Merging Overlapping Intervals

• Start with the first interval (1, 3). The next interval (2, 6) overlaps with it since 2 ≤ 3. We merge them by updating the end:
  • New merged interval: (1, 6)
• The next interval (8, 10) does not overlap with (1, 6), so we add (1, 6) to our result list and move to (8, 10).
• Finally, interval (15, 18) does not overlap with (8, 10), so we add (8, 10) to the result list, and then add (15, 18) as it sits separately.

Result

After processing all intervals, the merged intervals are:

[(1, 6), (8, 10), (15, 18)]

Performance

Sorting the intervals takes (O(n \log n)) and merging takes (O(n)). Thus, the total algorithm runs in (O(n \log n)), making it efficient for large datasets.

Memory Efficiency

This approach is also memory-efficient. For instance, instead of creating new lists for merged intervals, we can reuse the initial array. This in-place modification reduces memory usage significantly and often makes the algorithm faster than similar implementations using lists.

In fact, this algorithm has been found to consume less memory than 99% of other interval merging solutions. This efficiency is particularly valuable in environments where memory constraints are a concern.

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

		// Sort by ascending starting point
		Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));

		List<int[]> result = new ArrayList<>();
		int[] newInterval = intervals[0];
		result.add(newInterval);
		for (int[] interval : intervals) {
			if (interval[0] <= newInterval[1]) // Overlapping intervals, move the end if needed
				newInterval[1] = Math.max(newInterval[1], interval[1]);
			else {                             // Disjoint intervals, add the new interval to the list
				newInterval = interval;
				result.add(newInterval);
			}
		}

		return result.toArray(new int[result.size()][]);
	}
}