56. Merge Intervals

Q: 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].

Q: 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.

Q: 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).

mediumAsked at Gusto

Merge 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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

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^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

Examples

Example 1

Input

intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

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

Input

intervals = [[1,4],[4,5]]

Output

[[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.

Output

Press Run or Cmd+Enter to execute

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).

Practice these live with InterviewChamp.AI

Drill Merge Intervals and other Gusto interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →