1. Problem Statement

Given a list of intervals, merge all the overlapping intervals and return a list of non-overlapping intervals.

An interval is represented as a pair of integers [start, end].

Example

• Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
• Output: [[1,6],[8,10],[15,18]]
• Explanation: Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

2. Understanding the Problem

The core idea is to combine intervals that share common points. If two intervals [a,b] and [c,d] overlap, their merged form will be [min(a,c),max(b,d)].

Consider these scenarios for overlapping:

• Partial Overlap: [1,5] and [3,7] merge to [1,7].
• Complete Containment: [1,10] and [3,7] merge to [1,10].
• Touching (considered overlapping): [1,5] and [5,7] merge to [1,7].

3. Initial Thoughts and Approach

A brute-force approach might involve iterating through all pairs of intervals and merging them. However, this would lead to a time complexity of O(N2) where N is the number of intervals, which might be too slow for N=104.

A more efficient approach would involve sorting the intervals. If we sort the intervals based on their start times, we can then iterate through them sequentially and efficiently check for overlaps with the previous merged interval.

4. Step-by-Step Solution

Let’s outline the algorithm:

1. Sort the Intervals: Sort the given intervals list based on the start time of each interval. If start times are equal, you can sort by end times (though it’s not strictly necessary for correctness, it can sometimes lead to slightly more predictable behavior).
2. Initialize Result List: Create an empty list, let’s call it merged_intervals, to store the non-overlapping intervals.
3. Iterate and Merge:
   • If merged_intervals is empty, or if the current interval’s start time is greater than the end time of the last interval in merged_intervals, then the current interval does not overlap with the previous one. In this case, simply add the current interval to merged_intervals.
   • If the current interval does overlap with the last interval in merged_intervals (i.e., its start time is less than or equal to the end time of the last interval in merged_intervals), then merge them. Update the end time of the last interval in merged_intervals to be the maximum of its current end time and the current interval’s end time.

5. Java Implementation

import java.util.*;

public class MergeOverlappingIntervals {

    // Interval class
    static class Interval {
        int start;
        int end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }
    }

    // Function to merge overlapping intervals
    public static List<Interval> merge(List<Interval> intervals) {
        List<Interval> merged = new ArrayList<>();

        if (intervals == null || intervals.size() == 0) {
            return merged;
        }

        // Step 1: Sort intervals by start time
        intervals.sort(Comparator.comparingInt(i -> i.start));

        // Step 2: Initialize merged list with first interval
        Interval prev = intervals.get(0);
        merged.add(prev);

        // Step 3: Process each interval
        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(i);

            if (current.start <= prev.end) {
                // Overlapping intervals, merge them
                prev.end = Math.max(prev.end, current.end);
            } else {
                // No overlap, add to result
                merged.add(current);
                prev = current;
            }
        }

        return merged;
    }

    public static void main(String[] args) {
        // Sample input: [1,3], [2,6], [8,10], [15,18]
        List<Interval> input = Arrays.asList(
            new Interval(1, 3),
            new Interval(2, 6),
            new Interval(8, 10),
            new Interval(15, 18)
        );

        // Merge the intervals
        List<Interval> result = merge(input);

        // Print result
        System.out.println("Merged Intervals:");
        for (Interval interval : result) {
            System.out.println(interval);
        }
    }
}