Skip to main content

56. Merge Intervals

mediumAsked at Akamai

Merge all overlapping intervals and return the non-overlapping result. Akamai uses this to model time-range coalescing in traffic analytics — merging overlapping maintenance windows or caching TTL intervals across thousands of edge nodes is a direct application of this algorithm.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE onsite reports list Merge Intervals as a common array manipulation problem in algorithm rounds.
  • Blind (2025-11)— Multiple Akamai threads confirm interval merging problems appear regularly in system-design-adjacent coding sessions.

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 so they merge to [1,6].

Example 2

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

Explanation: Intervals touching at a boundary are considered overlapping.

Approaches

1. Sort by start, then linear merge

Sort intervals by start time. Iterate through: if the current interval overlaps the last merged interval (current.start <= last.end), extend the last interval's end. Otherwise, push the current interval as a new entry.

Time
O(n log n)
Space
O(n) 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 last = merged[merged.length - 1];
    const curr = intervals[i];
    if (curr[0] <= last[1]) {
      // Overlap: extend the end of the last merged interval
      last[1] = Math.max(last[1], curr[1]);
    } else {
      merged.push(curr);
    }
  }
  return merged;
}

Tradeoff: O(n log n) dominated by sorting. After sorting, the merge pass is a single O(n) scan. The sort is necessary — without it, overlapping intervals that aren't adjacent cannot be detected in a single pass.

Akamai-specific tips

State the sorting insight first: 'Once sorted by start time, I only need to compare each interval with the most recently merged one — no backtracking needed. The sort reduces the problem to a single O(n) scan.' Then walk through the overlap condition: current.start <= last.end covers both strict overlap and touching boundaries. Akamai probes for correctness at the boundary case explicitly.

Common mistakes

  • Not sorting first — unsorted intervals require O(n²) comparisons to find all overlaps.
  • Using current.end instead of Math.max(last.end, current.end) — misses the case where the current interval is fully contained within the last merged interval.
  • Modifying the input array in place without making a copy — may violate the caller's expectations; mention this as a defensive consideration.

Follow-up questions

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

  • Insert Interval (LC 57) — insert a new interval into a sorted non-overlapping list.
  • Meeting Rooms II (LC 253) — find the minimum number of meeting rooms required given all intervals.
  • How would you solve this if intervals arrive as a stream and you need to emit merged intervals in real time?

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 Math.max for the end, not just current.end?

If the current interval is fully contained within the last merged interval (e.g., [1,10] and [2,5]), taking current.end would shrink the merged interval. Math.max correctly handles containment.

Are intervals touching at a single point (like [1,4],[4,5]) considered overlapping?

Yes — the standard convention is that sharing an endpoint means overlapping. The condition current.start <= last.end (not strictly less than) handles this.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →