Skip to main content

56. Merge Intervals

mediumAsked at HP

HP enterprise IT scheduling tools manage maintenance windows, firmware update slots, and print-fleet reservation blocks. Overlapping intervals must be collapsed into non-overlapping ranges before scheduling can proceed. Merge Intervals is the canonical version of this problem, and HP uses it to test sort-then-sweep reasoning.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2026-Q1)— HP SWE onsite round reports list Merge Intervals as a recurring medium question in backend and systems roles.
  • Blind (2025-12)— HP interview prep threads recommend mastering Merge Intervals as a staple medium problem for HP technical screens.

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]]

Explanation: [1,3] and [2,6] overlap since 2 <= 3, so merge to [1,6].

Example 2

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

Explanation: Intervals touching at endpoint 4 are considered overlapping.

Approaches

1. Sort by start + linear sweep

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

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

Tradeoff: O(n log n) dominated by sort, then O(n) sweep. Sorting is the prerequisite that makes the single-pass merge possible. This is the canonical and expected solution.

HP-specific tips

HP interviewers want you to explicitly state that sorting by start time is necessary, not just a convenient pre-step. The key merge condition is current.start <= last.end (not strictly <), because touching intervals [1,4],[4,5] should merge. Always use Math.max for the new end — don't assume the current interval's end is always greater. Be ready to discuss how you'd handle inserting a new interval into an already-merged list (LC 57).

Common mistakes

  • Using strict less-than (current.start < last.end) — misses touching intervals.
  • Taking current.end instead of Math.max(last.end, current.end) when merging — fails for fully-contained intervals like [1,10] and [2,5].
  • Not sorting before sweeping — adjacent intervals in the input may not be in start-order.
  • Mutating the input array in place without copying — can cause subtle bugs if input is reused.

Follow-up questions

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

  • Insert a new interval into an already-merged list (LC 57).
  • What is the minimum number of intervals to remove to make all remaining intervals non-overlapping (LC 435)?
  • How would you merge intervals in a streaming fashion as new intervals arrive?

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 sort by start time specifically?

If intervals are sorted by start, any overlapping pair must be adjacent in the sorted order. This reduces the problem to a single linear pass.

What if multiple intervals are fully contained inside another?

Math.max(last.end, current.end) handles this: the inner interval's end is smaller than the outer's, so last.end is unchanged — correct behavior.

What is the time complexity if the input is already sorted?

O(n) — no sorting needed. The sweep alone is linear.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →