56. Merge Intervals
mediumAsked at GustoMerge all overlapping intervals. Gusto's scheduling and payroll features make this a naturally grounded problem — think PTO blocks, pay-period windows, or benefits-eligibility ranges. They want clean comparator logic and a crisp overlap condition.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Gusto loops.
- Glassdoor (2025-12)— Gusto SWE interview reports cite Merge Intervals as a problem that appears in onsite rounds with a practical scheduling framing.
- Blind (2025-10)— Listed in Gusto prep threads as a high-frequency medium that tests sorting and greedy merging simultaneously.
Problem
Given an array of intervals where intervals[i] = [starti, endi], 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 <= starti <= endi <= 10^4
Examples
Example 1
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]Explanation: [1,3] and [2,6] overlap (2 ≤ 3), so they merge to [1,6]. The others don't overlap.
Example 2
intervals = [[1,4],[4,5]][[1,5]]Explanation: Touching intervals (end equals start) are considered overlapping.
Approaches
1. Sort + greedy merge
Sort intervals by start time. Walk through them: if the current interval overlaps with the last merged interval (current.start <= last.end), extend last.end. Otherwise append a new interval.
- Time
- O(n log n)
- Space
- O(n) for output
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const [currStart, currEnd] = intervals[i];
const last = merged[merged.length - 1];
if (currStart <= last[1]) {
// overlap — extend the end of the last merged interval
last[1] = Math.max(last[1], currEnd);
} else {
merged.push([currStart, currEnd]);
}
}
return merged;
}Tradeoff: O(n log n) dominated by the sort. The greedy merge is O(n) after sorting. This is the canonical solution — no alternative approach gives better than O(n log n) since sorting is required.
Gusto-specific tips
State the overlap condition explicitly before coding: 'Two intervals overlap if and only if the start of the later interval is ≤ the end of the earlier one (after sorting by start).' Gusto interviewers often ask about touching intervals [1,4] and [4,5] — they should merge to [1,5] since start ≤ end means touching counts. Use Math.max to extend the end, not simple reassignment, to handle the case where a smaller interval is fully contained within a larger one.
Common mistakes
- Using currEnd > last[1] instead of currStart <= last[1] as the overlap condition — inverts the logic.
- Setting last[1] = currEnd instead of Math.max(last[1], currEnd) — fails for contained intervals like [1,10] followed by [2,5].
- Not sorting before merging — intervals can arrive out of order.
- Sorting by end time instead of start time — breaks the greedy merge logic.
Follow-up questions
An interviewer at Gusto may pivot to one of these next:
- Insert Interval (LC 57) — insert a new interval into a sorted non-overlapping list.
- Non-overlapping Intervals (LC 435) — find the minimum number of intervals to remove to make all intervals non-overlapping.
- How would you test this for a list of intervals where all are contained within one large interval?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Do touching intervals count as overlapping?
Yes — [1,4] and [4,5] share the point 4. The condition currStart <= last[1] includes equality, so they merge to [1,5].
What happens with a single-interval input?
The result array is initialised with intervals[0] and the loop doesn't execute. The single interval is returned unchanged — correct.
Is there an O(n) solution?
Only if the intervals are already sorted, which reduces it to the O(n) greedy merge pass. In general the sort is unavoidable, giving O(n log n).