Merge Intervals DSA Solution - Study Chapter | QuizMaker

Merge Intervals explained with pairwise brute force, optimized sort and sweep, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 10: Sorting & Searching

Learning Outcome

After this lesson, you should be able to sort intervals by start and maintain one active merged interval.

Problem Statement

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

Input	Output	Why
`intervals = [[1,3],[2,6],[8,10],[15,18]]`	`[[1,6],[8,10],[15,18]]`	[1,3] overlaps [2,6], so they merge into [1,6].

Brute Force Approach

Repeatedly compare every interval with every other interval until no merges remain. This is slow and easy to get wrong.

Optimized Approach

Sort intervals by start. Sweep from left to right and merge into the last interval when starts overlap.

Exact Pseudocode

sort intervals by start
merged = []
for interval in intervals:
  if merged is empty or interval.start > merged.last.end:
    add interval to merged
  else:
    merged.last.end = max(merged.last.end, interval.end)
return merged

Reference Code

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)

        return merged

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;

        for (auto& interval : intervals) {
            if (merged.empty() || interval[0] > merged.back()[1]) {
                merged.push_back(interval);
            } else {
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }

        return merged;
    }
};

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {
            if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {
                merged.add(interval);
            } else {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], interval[1]);
            }
        }

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

Sample Dry Run

Step	State	Result
Sort	Intervals already sorted by start	Ready to sweep
[1,3]	merged is empty	add [1,3]
[2,6]	2 <= 3	merge to [1,6]
[8,10]	8 > 6	start new interval

Complexity

Measure	Value	Reason
Time	O(n log n)	Sorting dominates the runtime.
Space	O(n)	The merged output can store all intervals.

Edge Cases

Touching intervals like [1,4] and [4,5] usually merge.
An empty interval list returns empty output.
Sorting by end time breaks the sweep invariant.

Interview Checklist

Sort by interval start.
Compare current start with last merged end.
Extend the last merged end with max end.

FAQs

Why sort first?

Sorting puts possible overlaps next to each other, so one left-to-right sweep is enough.

Why compare with the last merged interval?

After sorting, only the active last merged interval can overlap the current interval.

What is the core pattern?

Sort and sweep.