Q14: How do you Merge Overlapping Intervals in an array?

Sort the intervals by their start times: Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])).
Iterate through intervals and maintain a merged list. If the current interval's start time $le$ the last merged interval's end time, merge them by updating last.end = Math.max(last.end, current.end). Otherwise, append the current interval.

Merge Overlapping Intervals Solution

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

public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();
        int[] current = intervals[0];
        result.add(current);
        for (int[] interval : intervals) {
            if (interval[0] <= current[1]) {
                current[1] = Math.max(current[1], interval[1]);
            } else {
                current = interval;
                result.add(current);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

💡 Sorts intervals by start time and merges overlapping boundary spans in linear order.

Key Takeaways

Sorting by start time guarantees overlapping intervals are adjacent.
Time Complexity: $O(n log n)$ due to initial sorting pass.

Knowledge Check

What is the time complexity bottleneck in the Merge Intervals algorithm?

Q14: How do you Merge Overlapping Intervals in an array?

STAY UPDATED WITH BYTES!