Merge Intervals medium

Problem Statement

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] overlaps, 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.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This ensures that we process overlapping intervals together. We use a custom comparator for this.

2. Initialize the merged intervals list: Create a list to store the merged intervals. The first interval from the sorted list will always be part of the merged intervals.

3. Iterate and merge: Iterate through the sorted intervals. For each interval:

   • If the current interval overlaps with the last interval in the merged list (its start time is less than or equal to the end time of the last merged interval), merge them by updating the end time of the last merged interval to the maximum of the current interval's end time and the last merged interval's end time.
   • If there's no overlap, add the current interval to the merged intervals list.

4. Return the merged intervals: After processing all intervals, the merged intervals list contains the non-overlapping intervals covering all input intervals.

Explanation

The algorithm's core idea is based on sorting and greedy approach. Sorting allows us to process intervals in a sequential manner, making it easier to identify and handle overlaps. The greedy approach, in choosing the maximum end time during merging, ensures we find the minimal set of non-overlapping intervals that cover all input intervals.

Code

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }

        // Sort intervals by start time
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        List<int[]> mergedIntervals = new ArrayList<>();
        mergedIntervals.add(intervals[0]); // Add the first interval

        for (int i = 1; i < intervals.length; i++) {
            int[] currentInterval = intervals[i];
            int[] lastMergedInterval = mergedIntervals.get(mergedIntervals.size() - 1);

            // Check for overlap
            if (currentInterval[0] <= lastMergedInterval[1]) {
                // Merge intervals
                lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
            } else {
                // No overlap, add current interval
                mergedIntervals.add(currentInterval);
            }
        }

        // Convert List<int[]> to int[][]
        return mergedIntervals.toArray(new int[0][]);
    }
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step. N is the number of intervals.
• Space Complexity: O(N) in the worst case (when no intervals overlap), to store the merged intervals. In the best case (all intervals overlap), it's O(1). The space used for sorting might vary depending on the sorting algorithm used by Arrays.sort(). In many Java implementations, it's O(log N) extra space for recursion.