51. Merge Intervals

Q: Why does sorting by start make linear sweep correct?

Once sorted, any interval that overlaps with the merged current MUST start at or before current.end. After current ends, no later interval can overlap (they all start later).

Q: What if intervals are sorted by end instead?

Sorting by end is useful for the greedy 'min intervals to remove' problem (LC 435) but not for merging.

mediumAsked at Salesforce

Merge overlapping intervals in a list. Salesforce uses this as a foundational scheduling problem — they use it directly in their calendar conflict-resolution and queue-coalescing logic.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

Glassdoor (2026-Q1)— Salesforce Calendar/Activity team uses interval merging in production.
Blind (2025-12)— Recurring on Salesforce L4/L5 onsites.

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

Examples

Example 1

Input

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

Output

[[1,6],[8,10],[15,18]]

Example 2

Input

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

Output

[[1,5]]

Approaches

1. Brute force pairwise merge

For each pair, if they overlap, merge them. Repeat until no merges happen.

Time: O(n^3) worst
Space: O(n)

// Not feasible — pairwise repeat-until-stable is too slow.

Tradeoff: TLE. Salesforce wants the sort + sweep approach.

2. Sort by start, then linear sweep

Sort by start. Maintain a current interval; if next starts before current ends, extend current.end; else push current and start new.

Time: O(n log n)
Space: O(n) for output

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [];
  for (const [s, e] of intervals) {
    if (result.length && s <= result[result.length - 1][1]) {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], e);
    } else {
      result.push([s, e]);
    }
  }
  return result;
}

Tradeoff: O(n log n) for the sort dominates. The linear sweep is the canonical interval-merge pattern.

Salesforce-specific tips

Salesforce uses this in their Calendar app's conflict detection and in Bulk API job coalescing. They grade on whether you reach for sort-by-start immediately. Bonus signal: discuss that for online (streaming) input, you'd use a balanced BST keyed on start — Salesforce's queue system uses this exact pattern.

Common mistakes

Forgetting to compare to the LAST in result (could overlap with the second-to-last after extending, but the sort guarantees this doesn't happen — explain the proof).
Using s < end instead of s <= end — gives wrong answer when intervals touch (e.g., [1,4] and [4,5] should merge to [1,5]).
Not handling empty input.

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

Insert Interval (LC 57) — insert a new interval into a sorted list.
Meeting Rooms II (LC 253) — minimum number of rooms.
Non-overlapping Intervals (LC 435).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does sorting by start make linear sweep correct?

Once sorted, any interval that overlaps with the merged current MUST start at or before current.end. After current ends, no later interval can overlap (they all start later).

What if intervals are sorted by end instead?

Sorting by end is useful for the greedy 'min intervals to remove' problem (LC 435) but not for merging.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →