56. Merge Intervals

Q: Why sort by start and not end?

After sorting by start, any interval that overlaps the previous one must have a start <= previous end. Sorting by end would not give this clean property.

Q: Does this work if intervals are already sorted?

Yes — the sort is a no-op (stable sort of already-sorted data) and the sweep still works correctly in O(n).

Q: What if two intervals have the same start time?

Sorting by start puts them adjacent; the merge condition (curr.start <= last.end) still works correctly regardless of which order they appear within the same start time.

mediumAsked at eBay

eBay's seller calendar and auction scheduling system must merge overlapping time windows — two auctions that overlap should be shown as a single block. Merge Intervals is a practical sorting-and-sweep problem that eBay uses to test systematic interval reasoning and clean boundary condition handling.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

Glassdoor (2025-12)— Reported as a common eBay medium interval problem in onsite rounds for mid-level SWEs.
Blind (2025-09)— eBay interview prep threads list Merge Intervals as a high-frequency problem with an emphasis on clean boundary handling.

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

Example 2

Input

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

Output

[[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping (touching at 4).

Approaches

1. Sort by start + greedy sweep

Sort intervals by start time. Iterate; if the current interval overlaps the last merged interval (current.start <= last.end), extend the last merged 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
      last[1] = Math.max(last[1], curr[1]);
    } else {
      merged.push(curr);
    }
  }
  return merged;
}

Tradeoff: O(n log n) dominated by sorting. The sweep itself is O(n). This is the canonical O(n log n) solution — sorting is the prerequisite for the greedy property to hold.

eBay-specific tips

eBay interviewers test two boundary conditions: (1) touching intervals [1,4],[4,5] — overlap because curr.start (4) <= last.end (4); (2) contained intervals [1,10],[2,5] — use Math.max(last[1], curr[1]) not just curr[1], or you'd shrink the merged interval. State these two cases explicitly before coding. Also mention that if intervals were already sorted, the sort step is O(n) and the total drops to O(n).

Common mistakes

Using last[1] = curr[1] instead of Math.max(last[1], curr[1]) — breaks when the current interval is entirely contained within the last merged interval.
Using curr[0] < last[1] instead of <= — misses touching intervals like [1,4],[4,5].
Not sorting by start time first — the greedy merge only works on sorted intervals.
Mutating the input array during the sort if the caller expects it unchanged — create a sorted copy if immutability matters.

Follow-up questions

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

Insert Interval (LC 57) — insert a new interval into an already sorted, merged list and re-merge.
Non-overlapping Intervals (LC 435) — find the minimum number of intervals to remove to make the rest non-overlapping.
How would you handle this if intervals could have fractional boundaries (floating-point start/end)?

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 and not end?

After sorting by start, any interval that overlaps the previous one must have a start <= previous end. Sorting by end would not give this clean property.

Does this work if intervals are already sorted?

Yes — the sort is a no-op (stable sort of already-sorted data) and the sweep still works correctly in O(n).

What if two intervals have the same start time?

Sorting by start puts them adjacent; the merge condition (curr.start <= last.end) still works correctly regardless of which order they appear within the same start time.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →