Merge Intervals is the gateway to every interval problem you will ever be asked, and it is carried almost entirely by one decision made before the first line of logic: sort by start time. Get that right and the rest is a six-line loop. Get it wrong and no amount of careful case analysis rescues it.
The problem
Given an array of intervals [start, end], merge all overlapping intervals and return
the non-overlapping intervals that cover all the input.
[[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]
[[1,4],[4,5]] -> [[1,5]] touching counts as overlapping
[[1,4],[0,4]] -> [[0,4]] input is not sorted
[[1,4],[2,3]] -> [[1,4]] fully contained
[[1,4],[5,6]] -> [[1,4],[5,6]]Why sorting is the whole algorithm
Unsorted, "does this interval overlap anything I have already emitted?" is a question about the
entire output so far, and answering it for every input is O(n²). Worse, merging two
intervals can create a wider one that now overlaps something you emitted earlier, so you cannot even
trust what you have already written down.
Sorting by start time removes both problems at once. Process the intervals in that order and the one you are holding can only ever overlap the most recent interval in the output. It cannot reach further back, because everything before that ended even earlier — no, more precisely: every earlier interval started earlier, and if the current one overlapped it, the most recent output would have already been widened to cover it.
That reduces the question from "does it overlap anything?" to "does it overlap the last one?", which is one comparison.
The overlap test, and the two ways to get it wrong
last = [1,4], current = [4,5]
overlap when current.start <= last.end 4 <= 4 -> merge to [1,5]
merged end is max(last.end, current.end)Use <=, not <. Whether [1,4] and
[4,5] merge is a question about the problem, not about your code, and LeetCode says they
do. Ask it aloud if it is not stated — for meeting rooms the answer is usually no, for numeric
ranges usually yes, and the interviewer is often waiting to see whether you notice there is a
question at all.
Take the max of the ends. Writing last.end = current.end looks
natural after sorting and is wrong on [[1,10],[2,3]], which would produce
[1,3] and drop everything from 3 to 10. Sorting by start says nothing about the ends: a
later interval can be entirely swallowed by an earlier one. This is the single most common bug in
the problem.
Java
class Solution {
public int[][] merge(int[][] intervals) {
// Integer.compare, not a[0] - b[0]: the subtraction overflows on large bounds.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
if (last != null && interval[0] <= last[1]) {
last[1] = Math.max(last[1], interval[1]); // max, NOT interval[1]
} else {
// Copy rather than add `interval` -- we mutate last[1] above, and
// that would write into the caller's array.
merged.add(new int[]{interval[0], interval[1]});
}
}
return merged.toArray(new int[merged.size()][]);
}
}Two things in there are worth saying out loud rather than leaving as comments.
(a, b) -> a[0] - b[0] is the comparator everybody writes and it is broken for
inputs spanning the integer range: Integer.MIN_VALUE - 1 wraps to a positive number and
the sort silently produces garbage. It will pass every test in this problem and fail in production.
Copying the interval before adding it matters because the loop mutates last[1] in
place. Adding the caller's array and then writing to it means the function quietly modifies its own
input, which is a bug of the kind that surfaces three call sites away.
Python
class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
merged: list[list[int]] = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end]) # a copy, not the caller's list
return mergedsorted(intervals) compares lists element by element, so it sorts by start and breaks
ties by end — which is exactly what is wanted and costs no extra key function. Being able to say
why the bare sorted is correct here is better than writing
key=lambda x: x[0] out of caution.
Complexity
| Time | Space | |
|---|---|---|
| Sort | O(n log n) | O(log n) to O(n) |
| Merge pass | O(n) | O(n) output |
The sort dominates, and there is no way around it in the comparison model: merging intervals
lets you sort numbers, so a sub-O(n log n) merge would be a sub-O(n log n)
sort. That reduction is a genuinely good thing to offer when asked "can you do better?" — the answer
is no, and you can say why.
If the input arrives already sorted, the problem is
Insert Interval's situation and the
whole thing is O(n).
Sort by start, or sort by end?
Both appear in interval problems and they are not interchangeable:
| Sort by | Use it for |
|---|---|
| start | merging, union, "how much is covered" |
| end | choosing a maximum non-overlapping set — finish early, keep options open |
Non-overlapping Intervals (435) and Minimum Number of Arrows (452) sort by end, because there the greedy is "always keep the interval that frees you up soonest". Reaching for start-sorting on those produces a plausible answer that is quietly not optimal.
The pattern
Insert Interval (57) is this
merge with the sort already done for you. Meeting Rooms (252) is "did any merge happen?".
Meeting Rooms II (253) asks for the peak overlap, which drops the intervals entirely and sweeps a
timeline of +1 at each start and -1 at each end. Interval List
Intersections (986) walks two sorted lists together instead of one.
The reusable move is the same every time: sort the endpoints into an order that makes the answer local, then take one pass.
What the interviewer is checking
- That sorting by start is the first thing you say, and that you can justify it.
Math.max(last[1], interval[1])— the contained-interval case.- That you raise the touching-intervals question rather than silently picking a side.
Integer.compareover subtraction in the comparator.- That you do not mutate the caller's arrays.
- Single interval and empty input.
- That you know when to sort by end instead.