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

Intervals

Guide 5 of 6 · Path 5 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,2]
[1,3]
[2,3]
[3,4]

Min removals so intervals do not overlap. Sort by end.

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

Mediumintervalsgreedy

Non-overlapping Intervals

Problem (restated)

Given intervals, return the minimum number of intervals to remove so the rest are non-overlapping. Endpoints may touch (end == next.start is fine).

Intuition

Maximizing kept intervals is classic activity selection: always keep the interval that finishes earliest so more room remains for later ones. Removals = n - kept.

Approaches

Sort by end + greedy keep

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

Idea. Sort by end ascending. Track keptEnd. If next starts before keptEnd, discard it (count +1); else keep it and update keptEnd.

Walkthrough. [[1,2],[2,3],[3,4],[1,3]] → sort by end: [1,2],[1,3],[2,3],[3,4]. Keep [1,2], drop [1,3], keep [2,3], keep [3,4] → 1 removal.

Trade-offs. Sorting by start and always dropping the one with later end is equivalent but slightly more bookkeeping. DP over sorted intervals is correct but slower to code.

Solution
export function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals = [...intervals].sort((a, b) => a[1]! - b[1]!);
  let keptEnd = intervals[0]![1]!;
  let removals = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i]![0]! < keptEnd) removals++;
    else keptEnd = intervals[i]![1]!;
  }
  return removals;
}

export function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals = [...intervals].sort((a, b) => a[1]! - b[1]!);
  let keptEnd = intervals[0]![1]!;
  let removals = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i]![0]! < keptEnd) removals++;
    else keptEnd = intervals[i]![1]!;
  }
  return removals;
}

Template connection

Greedy scheduling on intervals: sort key is end, not start. Contrast with Merge Intervals (sort by start).

Reflection