Skip to main content

24. Merge Intervals

mediumAsked at Tripadvisor

Collapse overlapping date ranges into minimal non-overlapping blocks — Tripadvisor applies this interval-merge pattern constantly: consolidating overlapping hotel availability windows, booking blackout periods, and trip-leg date ranges for seamless itinerary display.

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

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: Intervals [1,3] and [2,6] overlap, merged to [1,6].

Example 2

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

Explanation: Intervals touching at 4 are considered overlapping.

Approaches

1. Brute force pairwise merge

For every pair of intervals, check overlap and merge. Repeat until no merges occur. Quadratic and impractical for large inputs.

Time
O(n^2)
Space
O(n)
function merge(intervals) {
  let changed = true;
  while (changed) {
    changed = false;
    const merged = [];
    const used = new Array(intervals.length).fill(false);
    for (let i = 0; i < intervals.length; i++) {
      if (used[i]) continue;
      let [s, e] = intervals[i];
      for (let j = i + 1; j < intervals.length; j++) {
        if (!used[j] && intervals[j][0] <= e) {
          e = Math.max(e, intervals[j][1]);
          used[j] = true;
          changed = true;
        }
      }
      merged.push([s, e]);
    }
    intervals = merged;
  }
  return intervals;
}

Tradeoff:

2. Sort then single-pass merge (optimal)

Sort intervals by start time. Iterate once: if the current interval overlaps the last merged result, extend its end; otherwise push a new interval.

Time
O(n log n)
Space
O(n)
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      result.push(intervals[i]);
    }
  }
  return result;
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor deal pages and availability calendars merge date ranges constantly — hotel blackout periods, special-event pricing windows, and multi-leg trip date blocks. Interviewers expect you to recognize the sort-first pattern immediately and to handle the edge case where intervals merely touch (start of one equals end of another) — that's a merge too. Always clarify whether touching intervals are considered overlapping before coding.

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 Tripadvisor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →