Merge Intervals

"Merge Intervals" is one of those classic algorithm problems that shows up frequently in technical interviews. It's a great test of your understanding of sorting, array manipulation, and edge case handling. In real-world scenarios, this type of logic appears in scheduling applications, calendar merging, or optimizing task execution windows.

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.

1. Clarify Requirements Before Jumping Into Code

• Are the intervals sorted? No.

• Can an interval be fully contained within another? Yes.

• Will the input have at least one interval? Yes.

• What should we return if there are no overlapping intervals? Return the original intervals.

2. Identify the Category of the Question 

This problem resembles a greedy algorithm because we can make local decisions (combine two overlapping intervals) that lead to a globally correct result, which is the hallmark of a greedy strategy. There's no need to backtrack or reconsider previous choices, making the greedy approach both efficient and straightforward here.

3. Consider a Brute-Force Approach to Understand the Problem

The brute-force approach would be to compare every interval with every other interval. If they overlap, we merge accordingly. But since we are scanning the whole array for every element, we get a runtime of O(n^2), which is not great.

Time Complexity: O(n^2), which is not efficient for larger inputs.

4. Brainstorm More Solutions

Part of the reason our brute-force solution is so inefficient is because overlapping intervals can be found anywhere in our input array. Our O(n^2) runtime comes from the fact that we have to scan the whole array on every iteration.

If we knew for a fact that overlapping intervals could be found immediately next to each other, then we wouldn't have to scan the whole array for a match. In fact, we could solve the problem with just one pass through the array because all we would need to do is compare an element against it's immediate neighbors.

So, as an optimization, let's start by sorting our array. We can do that in O(n log n) time.

Then, we iterate through our array:

• If the current interval overlaps with the previous one, merge them.

• Otherwise, add the current interval to the result.

Time Complexity: O(n log n)

5. Discuss Trade-Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute-force	O(n^2)	O(n)	Simple to implement	Very inefficient for large n
Greedy after sorting	O(n log n)	O(n)	Efficient, clean, widely applicable	Slightly more complex logic

6. Write Pseudocode to Structure Your Thoughts

function mergeIntervals(intervals):
    if intervals is empty:
        return []

    sort intervals by start time
    merged = [intervals[0]]

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

    return merged

7. Consider Edge Cases

• Only one interval: should return that interval.

• Completely overlapping intervals.

• No overlaps at all.

• Nested intervals (e.g., [1,10], [2,3]).

8. Write Full Code Syntax

import java.util.*;

public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];

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

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

        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            int[] current = intervals[i];
            if (current[0] <= last[1]) {
                last[1] = Math.max(last[1], current[1]);
            } else {
                merged.add(current);
            }
        }

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

9. Test Your Code

assert merge([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
assert merge([[1,4],[4,5]]) == [[1,5]]
assert merge([[1,4],[2,3]]) == [[1,4]]
assert merge([[1,4],[0,2],[3,5]]) == [[0,5]]
assert merge([[1,4]]) == [[1,4]]

10. Key Lessons to Remember for Future Questions

• Sorting often simplifies interval-related problems.

• Always consider edge cases like containment and exact overlaps.

• A single-pass greedy approach after sorting is a powerful pattern for these kinds of problems.

• Keep code clean and readable by separating concerns: sorting, iterating, and merging.

Good Luck and Happy Coding!