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. 💡 Hint

[1, 3]

[2, 6]

[8, 10]

[15, 18]

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]]

Sort: First, sort the intervals by their start time. [[1, 3], [2, 6], [8, 10], [15, 18]]
Initialize: Create a merged list and add the first sorted interval to it. merged = [[1, 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.

Merging Overlapping Intervals

The Approach: Sort and Merge

Code Implementation

Complexity Analysis

More Problems & Variations