22. Merge Intervals
easyAsked at DoordashCollapse a pile of possibly-overlapping intervals into the minimal set of disjoint spans — the canonical sort-then-sweep greedy, and one of the most practically-loaded easies in the catalog. DoorDash candidates report it with the scheduling flavor played straight: delivery time windows and Dasher shift blocks ARE interval merges, and the interview's real currency is naming the pattern (sort by start, then one linear pass extending or appending) before any code appears.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Doordash loops.
- LeetCode (2026)— Problem #56 'Merge Intervals' — canonical statement and bounds; a fixture of the most-asked interval questions industry-wide.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with DoorDash interview prep.
Problem
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.
Constraints
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^4
Examples
Example 1
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]Explanation: Intervals [1,3] and [2,6] overlap; merged to [1,6].
Example 2
intervals = [[1,4],[4,5]][[1,5]]Explanation: Touching at 4 counts as overlapping.
Approaches
1. Brute force nested comparison
Compare every pair of intervals to find overlaps; merge and restart. O(n^2) passes until stable.
- Time
- O(n^2)
- Space
- O(n)
function merge(intervals) {
let changed = true;
while (changed) {
changed = false;
const result = [];
const used = new Array(intervals.length).fill(false);
for (let i = 0; i < intervals.length; i++) {
if (used[i]) continue;
let [s, e] = intervals[i];
for (let j = i + 1; j < intervals.length; j++) {
if (used[j]) continue;
const [s2, e2] = intervals[j];
if (s2 <= e && e2 >= s) {
s = Math.min(s, s2); e = Math.max(e, e2);
used[j] = true; changed = true;
}
}
result.push([s, e]);
}
intervals = result;
}
return intervals;
}Tradeoff: Repeated full-pair scans until a fixed point — quadratic per pass and ugly to reason about. Its only use is making the sorted version's elegance obvious; don't write it out in an interview, just name why sorting kills the problem.
2. Sort then linear scan
Sort by start time; single pass merging the current interval into the last merged interval whenever they overlap. Classic greedy approach.
- Time
- O(n log n)
- Space
- O(n)
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.push(intervals[i]);
}
}
return merged;
}Tradeoff: O(n log n) for the sort, then a single O(n) sweep — optimal, since merging unsorted intervals fundamentally requires ordering them. The key invariant to narrate: after sorting by start, an interval can only overlap the LAST merged span, never an earlier one.
Doordash-specific tips
Doordash interviewers expect you to immediately connect intervals to real scheduling — 'how would you handle Dasher availability windows that span midnight?' The follow-up is almost always: what if intervals arrive as a stream? That pushes you toward a sorted structure (BST or sorted list with binary search insertion). Name the pattern — greedy after sort — before diving into code.
Common mistakes
- Merging only when start < lastEnd — touching intervals like [1,4] and [4,5] must merge too; the comparison is <=.
- Pushing a copy of intervals[i] but then mutating the original reference — keep one convention or merged spans silently desync.
- Taking max(last[1], current[1]) is mandatory — [1,10] followed by [2,3] must NOT shrink the end to 3.
- Sorting by end instead of start — the single-pass invariant breaks and you merge across gaps.
Follow-up questions
An interviewer at Doordash may pivot to one of these next:
- Insert Interval (LC 57): one new interval into an already-merged list — binary search plus a local merge.
- Meeting Rooms II (LC 253): instead of merging, count the maximum overlap depth — sweep line or min-heap of end times.
- Streaming intervals: maintain merged spans as they arrive — an ordered map keyed by start, with neighbor checks on insert.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why must the intervals be sorted first?
Sorting by start guarantees that all intervals which could merge with the current span are adjacent in the scan. Without it, an overlap can appear anywhere and you're back to quadratic pair-checking — the sort is what buys the single pass.
Why can a new interval only overlap the last merged span?
Because starts are non-decreasing: if intervals[i] doesn't reach back into the last span (start > lastEnd), it certainly can't reach any earlier span, whose ends are even smaller. That's the one-sentence proof worth saying aloud.
Do touching endpoints count as overlapping?
In this problem, yes — [1,4] and [4,5] merge to [1,5], which is why the comparison is start <= lastEnd. In booking-style variants touching is often allowed to coexist; always confirm which semantics the interviewer wants.