56. Merge Intervals

Q: Why do touching intervals merge?

The problem defines overlapping as curr.start <= last.end — equal endpoints are included, so [1,4] and [4,5] share point 4 and merge into [1,5].

Q: Can I avoid sorting?

Only if intervals are already sorted by start. If inputs can be unsorted, sorting is necessary for the greedy approach to work correctly.

Q: What's the difference between Merge Intervals and Insert Interval?

Insert Interval (LC 57) assumes the list is already merged and sorted — you insert one new interval, merge as needed, and return the updated list. Merge Intervals starts with an arbitrary unsorted list.

mediumAsked at Broadcom

Merge all overlapping intervals into the minimum set of non-overlapping intervals. Broadcom asks this because interval merging is core to TCAM rule compression in switching ASICs — overlapping ACL rules must be collapsed to minimise ternary content-addressable memory consumption.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

Glassdoor (2026-Q1)— Reported in Broadcom SWE onsite notes for networking software roles as an interval-manipulation problem.
Blind (2025-10)— Broadcom threads cite Merge Intervals as a medium problem that tests sorting and greedy merging logic.

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 since 2 <= 3; merged into [1,6].

Example 2

Input

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

Output

[[1,5]]

Explanation: Touching intervals [1,4] and [4,5] are considered overlapping.

Approaches

1. Sort by start + greedy merge

Sort intervals by start time. Walk through sorted intervals maintaining the last merged interval. If the current interval overlaps (start <= last.end), extend last.end. Otherwise push the current as a new interval.

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];
    const curr = intervals[i];
    if (curr[0] <= last[1]) {
      // Overlapping — extend the end if needed
      last[1] = Math.max(last[1], curr[1]);
    } else {
      merged.push(curr);
    }
  }
  return merged;
}

Tradeoff: O(n log n) dominated by sort. The merge pass itself is O(n). This is optimal — you need at least O(n log n) to establish relative order unless intervals arrive pre-sorted.

Broadcom-specific tips

Lead with the sort-by-start insight: 'Once sorted by start, I only need to compare each interval with the last merged interval — no backtracking needed.' At Broadcom, connect to ACL rule merging: 'In TCAM allocation, adjacent or overlapping IP prefix ranges are merged to minimise entries.' Also note that touching intervals [1,4] and [4,5] count as overlapping — check curr.start <= last.end, not strictly less than.

Common mistakes

Using curr.start < last.end (strict less-than) and missing touching intervals where start equals end.
Not using Math.max when extending last.end — a contained interval (e.g., [1,10] followed by [2,6]) must not shrink the end.
Forgetting to sort before merging — the greedy property only holds on a sorted sequence.
Initialising merged with an empty array and not pushing intervals[0] — results in comparing against undefined.

Follow-up questions

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

Insert Interval (LC 57) — insert a new interval into an already-merged sorted list.
Non-overlapping Intervals (LC 435) — find the minimum number of intervals to remove to eliminate all overlaps.
What if intervals are added dynamically one at a time (online interval tree)?

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 do touching intervals merge?

The problem defines overlapping as curr.start <= last.end — equal endpoints are included, so [1,4] and [4,5] share point 4 and merge into [1,5].

Can I avoid sorting?

Only if intervals are already sorted by start. If inputs can be unsorted, sorting is necessary for the greedy approach to work correctly.

What's the difference between Merge Intervals and Insert Interval?

Insert Interval (LC 57) assumes the list is already merged and sorted — you insert one new interval, merge as needed, and return the updated list. Merge Intervals starts with an arbitrary unsorted list.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →