Skip to main content

56. Merge Intervals

mediumAsked at LinkedIn

Merge all overlapping intervals in a list into non-overlapping ranges — LinkedIn uses this pattern to consolidate overlapping employment date ranges in member profiles and to compact calendar availability windows, making it one of the most practically grounded problems in their interview bank.

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

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 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, merging to [1,6]. The rest are disjoint.

Example 2

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

Explanation: Intervals touch at 4, which counts as overlapping.

Approaches

1. Brute force — check every pair

For each interval, scan all other intervals for overlap and merge. O(n^2) and messy to implement correctly. Only name this to justify the sort-first approach.

Time
O(n^2)
Space
O(n)
// O(n^2) brute force is impractical — shown only as a starting point.
// Sort-first reduces this to O(n log n) with a single linear scan.

Tradeoff:

2. Sort by start + single linear scan — optimal

Sort intervals by start time. Initialize result with the first interval. For each subsequent interval: if its start <= result.last.end, extend result.last.end to max of both ends; 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 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]) {
      last[1] = Math.max(last[1], curr[1]);
    } else {
      merged.push(curr);
    }
  }
  return merged;
}

Tradeoff:

LinkedIn-specific tips

LinkedIn often frames this as 'deduplicate a user's employment history — two overlapping date ranges at the same company should appear as one continuous stint.' Frame your solution in that language. The merge condition (curr.start <= last.end) handles touching intervals (e.g., [1,4],[4,5] → [1,5]) — confirm this edge case aloud. Common follow-up: 'insert a new interval into an already-merged list' (LC 57, Insert Interval) — the same sort-and-scan logic, but you can binary search for the insertion point.

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

Practice these live with InterviewChamp.AI →