Merge Overlapping Intervals in Java

Problem Statement

You are given an array of intervals where intervals[i] = [start_i, end_i]. Merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example

Input:

intervals = [[1,3],[2,6],[8,10],[15,18]]

Output:

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

Explanation:

• [1,3] and [2,6] overlap, so they are merged into [1,6].

Approach

1. Sort the intervals by the start time.
2. Initialize a list to hold merged intervals.
3. Loop through the intervals:
   • If the current interval overlaps with the previous, merge them.
   • Else, add the current interval as is.

Java Code

import java.util.*;

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

        // Sort by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();

        int[] current = intervals[0];
        merged.add(current);

        for (int[] interval : intervals) {
            int currentEnd = current[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            if (currentEnd >= nextStart) {
                // Merge
                current[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap
                current = interval;
                merged.add(current);
            }
        }

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

    public static void main(String[] args) {
        int[][] intervals = { {1,3}, {2,6}, {8,10}, {15,18} };
        int[][] result = merge(intervals);

        System.out.println("Merged Intervals:");
        for (int[] interval : result) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

Test Output

Merged Intervals:
[1, 6]
[8, 10]
[15, 18]

Time and Space Complexity

• Time Complexity: O(n log n) due to sorting.
• Space Complexity: O(n) for the merged list.