Merge Intervals - Java Solution

1. Introduction

In this post, we'll address a common problem in interval manipulation, known as "Merge Intervals." This problem is essential in many computational geometry applications and scheduling algorithms. The goal is to merge all overlapping intervals in a given set of intervals.

Problem

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

Examples:

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

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

- Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

2. Solution Steps

1. Sort the intervals based on their start times.

2. Initialize an empty list to hold the merged intervals.

3. Iterate through the sorted intervals:

- If the list is empty or if the current interval does not overlap with the previous one, add it to the list.

- Otherwise, merge the current interval with the last interval in the list.

4. Return the list of merged intervals.

3. Code Program

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MergeIntervals {
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] merged = merge(intervals);
        for (int[] interval : merged) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }

    // Function to merge overlapping intervals
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        LinkedList<int[]> merged = new LinkedList<>();

        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }

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

Output:

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

Explanation:

1. merge: This function processes an array of intervals to merge overlapping ones.

2. The intervals are first sorted based on their starting points to facilitate merging.

3. The function then iterates through the sorted intervals, merging overlapping intervals by updating the end time of the last interval in the list if there's an overlap.

4. Non-overlapping intervals are simply added to the list.

5. This solution is efficient, with a time complexity of O(n log n) due to sorting, and the merging operation itself takes O(n) time.

6. The use of a LinkedList simplifies adding and updating intervals, ensuring that the space complexity remains O(n).