Merge Intervals problem and solutions in Java and Python

The Merge Intervals problem is a classic interval manipulation problem often asked in interviews. Let’s break it down step by step with Java and Python solutions.

🧩 Problem Statement

Given an array of intervals where each interval is represented as [start, end], merge all overlapping intervals and return an array of 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: Intervals [1,3] and [2,6] overlap → merge to [1,6]

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] overlap → merge to [1,5]

🧠 Approach

1. Sort intervals by start time.

2. Initialize a merged list with the first interval.

3. For each interval:

   • If current.start <= lastMerged.end → intervals overlap → merge: lastMerged.end = max(lastMerged.end, current.end)
   • Else → no overlap → append current to merged list.

4. Return merged list.

Time Complexity: O(n log n) → sorting dominates Space Complexity: O(n) → for output

✅ Java Solution

import java.util.*;

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

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

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

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= current[1]) { // overlap
                current[1] = Math.max(current[1], intervals[i][1]);
            } else {
                merged.add(current);
                current = intervals[i];
            }
        }
        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[][] merged = merge(intervals);

        for (int[] interval : merged) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

Output:

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

✅ Python Solution

def merge(intervals):
    if not intervals:
        return []

    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:  # overlap
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)

    return merged

# Example
intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge(intervals))  # Output: [[1,6],[8,10],[15,18]]

🧩 Edge Cases

1. Empty input → return []
2. Single interval → return the interval itself
3. Fully overlapping intervals → merge into one e.g., [[1,10],[2,3],[4,8]] → [[1,10]]
4. Adjacent intervals e.g., [[1,2],[2,3]] → [[1,3]] (depends if you consider touching intervals as overlapping)

🧭 Variations

1. Insert Interval – Insert a new interval into a list of non-overlapping intervals and merge.
2. Number of Intervals After Merging – Count intervals after merging.
3. Interval Intersection – Find common overlaps between two interval lists.
4. Maximum Overlapping Intervals – Find point with maximum overlaps.