Skip to main content

16. Merge Intervals

mediumAsked at Freshworks

Merge overlapping time intervals — Freshworks frames it directly as collapsing overlapping SLA-timer windows on a ticket's lifecycle.

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

Problem

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of non-overlapping intervals covering all the input.

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start <= end <= 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 (repeated scan)

Repeatedly scan for any pair that overlaps and merge them; stop when no overlap remains.

Time
O(n^2)
Space
O(n)
let changed = true;
while (changed) {
  changed = false;
  outer: for (let i=0;i<intervals.length;i++)
    for (let j=i+1;j<intervals.length;j++)
      if (overlap(intervals[i], intervals[j])) { intervals[i]=merge(intervals[i],intervals[j]); intervals.splice(j,1); changed=true; break outer; }
}
return intervals;

Tradeoff:

2. Sort by start, sweep once

Sort intervals by start. Walk through; if current overlaps the previous (end >= next.start), extend the previous end. Otherwise, push as new.

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

Tradeoff:

Freshworks-specific tips

Freshworks loves the SLA-window framing — explicitly say 'two intervals overlap iff a.start <= b.end and b.start <= a.end' before you code so they hear the invariant.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →