Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Intervals

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
[1,3]
[8,10]
[2,6]
[15,18]

Unsorted intervals. Sort by start first.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumintervals

Merge Intervals

Problem (restated)

Given intervals [start, end], merge all overlapping intervals and return the non-overlapping result covering the same ranges.

Intuition

Sort by start. Scan and either merge into the current open interval or push a new one when there is a gap.

Approaches

Sort by start + merge

Tested only
Time O(n log n)Space O(n)

Idea. Sort intervals by start. Keep a list of merged. If next.start ≤ last.end, last.end = max(last.end, next.end); else append next.

Walkthrough. [[1,3],[2,6],[8,10]] → merge first two to [1,6], then append [8,10].

Trade-offs. Sorting dominates. In-place tricks exist but are rarely worth it in interviews.

Solution
export function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0]! - b[0]!);
  const res: number[][] = [];
  for (const interval of intervals) {
    const last = res[res.length - 1];
    if (!last || interval[0]! > last[1]!) res.push([...interval]);
    else last[1] = Math.max(last[1]!, interval[1]!);
  }
  return res;
}

export function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0]! - b[0]!);
  const res: number[][] = [];
  for (const interval of intervals) {
    const last = res[res.length - 1];
    if (!last || interval[0]! > last[1]!) res.push([...interval]);
    else last[1] = Math.max(last[1]!, interval[1]!);
  }
  return res;
}

Template connection

Flagship intervals problem. sort then linear merge.

Reflection