Problem 30 - Merge Intervals

Explore our archive for previous posts.

Question

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.

Constraints:

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= starti <= endi <= 10^4

Approach

The approach is to first sort the intervals based on their start times. Then, iterate through the sorted intervals, merging overlapping ones and storing the merged intervals in a result list.

Sorting the intervals based on start time ensures that we can process them in a linear manner, and overlapping intervals will be adjacent in the sorted array.

For merging, we start with the first interval and consider it as the current interval. We iterate through the sorted intervals starting from the second interval. For each interval, we check if it overlaps with the current interval. If there's an overlap, we merge them into a single interval by taking the maximum end time of the two intervals. If there's no overlap, we add the current interval to the result list and update the current interval to the new interval. We continue this process for all intervals. Whenever we find an interval that doesn't overlap with the current merged interval, we add the current merged interval to the result list and start considering the new interval as the current interval. At the end of the iteration, the last merged interval (or the last interval if no merge occurred) will not be added to the result yet. We add this final merged interval to the result list.

Solution

Solve it here

class Solution {
    public int[][] merge(int[][] intervals) {
        // If there are 0 or 1 intervals, no merging is needed
        if (intervals.length <= 1) {
            return intervals;
        }
        
        // Sort the intervals based on their start times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> result = new ArrayList<>();
        int[] currentInterval = intervals[0];
        
        // Iterate through the sorted intervals
        for (int i = 1; i < intervals.length; i++) {
            // If current interval overlaps with last interval in result, merge them
            if (currentInterval[1] >= intervals[i][0]) {
                currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);
            } else {
                // If no overlap, add current merged interval to result and update current interval
                result.add(currentInterval);
                currentInterval = intervals[i];
            }
        }
        
        // Add the last merged interval to result
        result.add(currentInterval);
        
        // Convert result list to array and return
        return result.toArray(new int[result.size()][]);
    }
}

Time and space complexity

Time Complexity: The time complexity is O(n log n), where 'n' is the number of intervals. This is due to the sorting step. The merging step is done in linear time.

Space Complexity: The space complexity is O(n) as we store the merged intervals in the result list which grows linearly with input interval length.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!