Merging Overlapping Intervals

Imagine you're building a calendar application. A user inputs their meeting schedule, and it's a mess: [[9:00, 10:30], [12:00, 13:00], [10:00, 11:00]]. To display this cleanly, you need to merge the overlapping meetings. The [9:00, 10:30] and [10:00, 11:00] slots overlap and should be combined into a single [9:00, 11:00] block.

This is the merge intervals problem. Before reading on, try to solve this problem yourself.

Problem: Merge Intervals (LeetCode Link): 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. 💡 HintWhat if you process the intervals in a specific order? Would sorting them help?

The brute-force approach would be to compare every interval with every other interval, but that's inefficient. The key to solving this class of problems is to first sort the intervals by their start times.

The Approach: Sort and Merge

Once sorted, you can iterate through the intervals and merge them in a single pass.

Step-by-Step Walkthrough

Let's walk through the example: [[1, 3], [8, 10], [2, 6], [15, 18]]

1. Sort: First, sort the intervals by their start time. [[1, 3], [2, 6], [8, 10], [15, 18]]

2. Initialize: Create a merged list and add the first sorted interval to it. merged = [[1, 3]]

3. Iterate and Merge: Now, iterate through the remaining intervals.

   • Current Interval: [2, 6]

     • Compare with the last interval in merged: [1, 3].
     • Is there an overlap? The condition for an overlap is current_interval.start <= last_merged_interval.end. (Note that in some problems, "equals" would mean no overlap. Adjust according to the question)
     • Here, 2 <= 3 is true. So they overlap.
     • To merge, we update the end of the last interval in merged to be the maximum of the two end times: max(3, 6) = 6.
     • merged is now [[1, 6]].

   • Current Interval: [8, 10]

     • Compare with the last interval in merged: [1, 6].
     • Is 8 <= 6? No. There's no overlap.
     • When there's no overlap, add the current interval to the merged list.
     • merged is now [[1, 6], [8, 10]].

   • Current Interval: [15, 18]

     • Compare with the last interval in merged: [8, 10].
     • Is 15 <= 10? No. No overlap.
     • Add [15, 18] to merged.
     • merged is now [[1, 6], [8, 10], [15, 18]].

We've processed all intervals. The result is [[1, 6], [8, 10], [15, 18]].

If you need a video explanation, here is one

Code Implementation

You can directly translate the above steps into code.

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

    # 1. Sort intervals based on the start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for i in range(1, len(intervals)):
        current_interval = intervals[i]
        last_merged_interval = merged[-1]

        # 2. Check for overlap
        if current_interval[0] <= last_merged_interval[1]:
            # 3. Merge the intervals by updating the end time
            last_merged_interval[1] = max(last_merged_interval[1], current_interval[1])
        else:
            # 4. No overlap, add the new interval
            merged.append(current_interval)

    return merged

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

    // 1. Sort intervals based on the 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[] currentInterval = intervals[i];
        int[] lastMergedInterval = merged.get(merged.size() - 1);

        // 2. Check for overlap
        if (currentInterval[0] <= lastMergedInterval[1]) {
            // 3. Merge the intervals by updating the end time
            lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
        } else {
            // 4. No overlap, add the new interval
            merged.add(currentInterval);
        }
    }

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

std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) {
        return {};
    }

    // 1. Sort intervals based on the start time
    std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[0] < b[0];
    });

    std::vector<std::vector<int>> merged;
    merged.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); ++i) {
        std::vector<int>& current_interval = intervals[i];
        std::vector<int>& last_merged_interval = merged.back();

        // 2. Check for overlap
        if (current_interval[0] <= last_merged_interval[1]) {
            // 3. Merge the intervals by updating the end time
            last_merged_interval[1] = std::max(last_merged_interval[1], current_interval[1]);
        } else {
            // 4. No overlap, add the new interval
            merged.push_back(current_interval);
        }
    }

    return merged;
}

Complexity Analysis

• Time Complexity: $O(N log N)$, where $N$ is the number of intervals. The sorting step dominates the complexity. The merging process itself is a single linear scan, which is $O(N)$.
• Space Complexity: $O(N)$ in the worst case (or $O(log N)$ depending on the sort implementation) for storing the sorted intervals and the merged list.

Bonus Point: This is exactly how calendar apps like Google Calendar or Outlook consolidate your busy schedule. When you sync multiple calendars, they use this logic to merge all your appointments and show you clean, contiguous blocks of free and busy time.

More Problems & Variations

The "Sort and Merge" pattern is fundamental. Try applying it to these variations:

1. Insert Interval (LeetCode Link): Given a set of non-overlapping sorted intervals, insert a new interval and merge if necessary. 💡 HintThe list of intervals is already sorted. How can you iterate through it to find the correct place for the new interval? 💡 HintAs you iterate, what are the three possible relationships between an existing interval and the new one? (e.g., before, after, overlapping). 💡 HintWhen you find an interval that overlaps with your new interval, how do you combine them? What should the new start and end times be?
2. Non-overlapping Intervals (LeetCode Link): Given a set of intervals, find the minimum number of intervals you need to remove to make the rest non-overlapping. 💡 HintThis is a slightly different problem. After sorting, if two intervals overlap, which one should you remove to minimize future overlaps?