Intervals

What is an interval problem

An interval is a pair [start, end] representing a contiguous range. Interval problems ask you to reason about how ranges relate to each other — do they overlap? Can they be merged? How many are active at any point in time?

They appear in scheduling (can this meeting be booked?), resource allocation (how many servers are needed?), and genomics (do these gene regions intersect?). The universal first step is almost always the same: sort by start time. Sorting gives structure, and structure enables a single linear scan.

Overlap condition

Two intervals [a, b] and [c, d] overlap if and only if a <= d && c <= b.

Why: they do not overlap when one ends before the other starts — either b < c (first ends before second starts) or d < a (second ends before first starts). Negate both non-overlap cases and you get the overlap condition.

Mentally picture it: if the second interval starts at or before the first ends, and the first starts at or before the second ends, they must share at least one point.

function overlaps(a: [number, number], b: [number, number]): boolean {
  return a[0] <= b[1] && b[0] <= a[1]
}

Merged interval when two intervals overlap: [min(a, c), max(b, d)].

Merge Intervals (LC 56)

Problem: Given an array of intervals, merge all overlapping intervals and return the result.

Algorithm:

1. Sort by start time.
2. Iterate — if the current interval overlaps the last merged interval, extend the end. Otherwise append a new interval.

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0])

  const merged: number[][] = [intervals[0]]

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1]
    const [start, end] = intervals[i]

    if (start <= last[1]) {
      // Overlaps — extend the end of the last merged interval
      last[1] = Math.max(last[1], end)
    } else {
      // No overlap — start a new merged interval
      merged.push([start, end])
    }
  }

  return merged
}
// Time: O(n log n)  Space: O(n)

Common mistake: forgetting Math.max when extending the end. A fully contained interval like [1,10] followed by [2,3] must keep end 10, not shrink to 3.

Insert Interval (LC 57)

Problem: Insert a new interval into a sorted, non-overlapping list of intervals, merging as necessary.

Three-phase scan:

1. Add all intervals that end before the new interval starts (no overlap on the left).
2. Merge all intervals that overlap the new one — update the new interval’s bounds.
3. Add all remaining intervals (no overlap on the right).

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = []
  let i = 0
  const n = intervals.length

  // Phase 1: intervals entirely before newInterval
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i])
    i++
  }

  // Phase 2: merge overlapping intervals into newInterval
  while (i < n && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0])
    newInterval[1] = Math.max(newInterval[1], intervals[i][1])
    i++
  }
  result.push(newInterval)

  // Phase 3: intervals entirely after newInterval
  while (i < n) {
    result.push(intervals[i])
    i++
  }

  return result
}
// Time: O(n)  Space: O(n)  — input is already sorted

Non-Overlapping Intervals (LC 435)

Problem: Find the minimum number of intervals to remove so that the rest are non-overlapping.

Greedy insight: equivalent to finding the maximum set of non-overlapping intervals (activity selection), then subtracting from total. Always keep the interval with the earliest end time — it leaves the most room for future intervals.

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1])   // sort by END time — critical

  let kept = 0
  let lastEnd = -Infinity

  for (const [start, end] of intervals) {
    if (start >= lastEnd) {
      // No conflict — keep this interval
      kept++
      lastEnd = end
    }
    // Otherwise skip (remove) this interval
  }

  return intervals.length - kept
}
// Time: O(n log n)  Space: O(1)

Why sort by end, not start? Sorting by start and picking the shortest interval is incorrect — a short interval that starts late can block many future intervals. Earliest end time is the provably optimal greedy choice (see Greedy topic for the exchange argument proof).

Meeting Rooms I (LC 252)

Problem: Given meeting time intervals, determine if a person can attend all meetings (no overlaps).

function canAttendMeetings(intervals: number[][]): boolean {
  intervals.sort((a, b) => a[0] - b[0])

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) return false
  }
  return true
}
// Time: O(n log n)  Space: O(1)

After sorting by start, two consecutive meetings overlap iff the later one starts before the earlier one ends. One linear scan suffices.

Meeting Rooms II (LC 253)

Problem: Find the minimum number of conference rooms required.

Approach 1 — Min-heap

Greedily assign each meeting to the room whose meeting finishes earliest. If the earliest-ending room is still busy when the new meeting starts, open a new room.

class MinHeap {
  private heap: number[] = []

  push(val: number): void {
    this.heap.push(val)
    this.bubbleUp(this.heap.length - 1)
  }

  pop(): number {
    const top = this.heap[0]
    const last = this.heap.pop()!
    if (this.heap.length > 0) {
      this.heap[0] = last
      this.sinkDown(0)
    }
    return top
  }

  peek(): number { return this.heap[0] }
  size(): number { return this.heap.length }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1
      if (this.heap[parent] <= this.heap[i]) break
      ;[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]]
      i = parent
    }
  }

  private sinkDown(i: number): void {
    const n = this.heap.length
    while (true) {
      let smallest = i
      const left = 2 * i + 1, right = 2 * i + 2
      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right
      if (smallest === i) break
      ;[this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]]
      i = smallest
    }
  }
}

function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0])   // sort by start

  const endTimes = new MinHeap()

  for (const [start, end] of intervals) {
    if (endTimes.size() > 0 && endTimes.peek() <= start) {
      endTimes.pop()   // reuse the room that freed up earliest
    }
    endTimes.push(end)
  }

  return endTimes.size()   // rooms in use = rooms needed
}
// Time: O(n log n)  Space: O(n)

Approach 2 — Sweep line (chronological ordering)

Record every meeting start as +1 and every meeting end as -1. Sort all events by time (ends before starts on ties — a room frees before the next meeting uses it). Scan and track the running maximum.

function minMeetingRoomsSweep(intervals: number[][]): number {
  const events: [number, number][] = []

  for (const [start, end] of intervals) {
    events.push([start, 1])    // meeting starts: +1 room needed
    events.push([end, -1])     // meeting ends:   -1 room needed
  }

  // Sort by time; on tie, end events (-1) before start events (+1)
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1])

  let rooms = 0
  let maxRooms = 0

  for (const [, delta] of events) {
    rooms += delta
    maxRooms = Math.max(maxRooms, rooms)
  }

  return maxRooms
}
// Time: O(n log n)  Space: O(n)

The sweep line is more elegant for follow-up questions like “how many meetings are running at time T?” — just stop the scan early.

Employee Free Time (LC 759)

Problem: Given a list of employees’ working schedules (each a list of non-overlapping intervals), return the free time intervals common to all employees.

Approach: flatten all intervals into one list, merge them (like LC 56), then collect the gaps.

// Interval class as used in the problem
class Interval {
  constructor(public start: number, public end: number) {}
}

function employeeFreeTime(schedule: Interval[][]): Interval[] {
  // Flatten all employee schedules into one array
  const all: Interval[] = schedule.flat()
  all.sort((a, b) => a.start - b.start)

  // Merge overlapping intervals
  const merged: Interval[] = [all[0]]
  for (let i = 1; i < all.length; i++) {
    const last = merged[merged.length - 1]
    if (all[i].start <= last.end) {
      last.end = Math.max(last.end, all[i].end)
    } else {
      merged.push(all[i])
    }
  }

  // Gaps between consecutive merged intervals = free time
  const freeTime: Interval[] = []
  for (let i = 1; i < merged.length; i++) {
    freeTime.push(new Interval(merged[i - 1].end, merged[i].start))
  }
  return freeTime
}
// Time: O(n log n)  Space: O(n)  — n = total intervals across all employees

Minimum Arrows to Burst Balloons (LC 452)

Problem: Balloons are represented as horizontal intervals on the x-axis. An arrow shot at x bursts all balloons whose range covers x. Find the minimum arrows needed.

Greedy: sort by end coordinate. Shoot one arrow at the end of the first balloon — it bursts all balloons whose start is still before or at that point. Skip those and repeat.

function findMinArrowShots(points: number[][]): number {
  points.sort((a, b) => a[1] - b[1])   // sort by end

  let arrows = 1
  let arrowPos = points[0][1]

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > arrowPos) {
      // This balloon is not burst by the current arrow
      arrows++
      arrowPos = points[i][1]
    }
  }

  return arrows
}
// Time: O(n log n)  Space: O(1)

This is structurally identical to LC 435 (Non-Overlapping Intervals) — both reduce to activity selection.

The sweep line technique

When a problem asks about the maximum number of simultaneous events or conflicts at any point in time, convert intervals to events:

// Generic sweep line template
function maxSimultaneous(intervals: number[][]): number {
  const events: [number, number][] = []

  for (const [start, end] of intervals) {
    events.push([start, +1])   // something starts
    events.push([end,   -1])   // something ends
  }

  // Sort by time; process endings before beginnings at the same time
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1])

  let current = 0, peak = 0
  for (const [, delta] of events) {
    current += delta
    peak = Math.max(peak, current)
  }
  return peak
}

Applications:

• Meeting Rooms II (shown above)
• Maximum concurrent users on a server
• Skyline problem (uses a max-heap instead of a simple counter)
• Hospital patient census — how many patients are admitted at once?

The key decision is how to break ties when two events share a timestamp. Ending before starting (-1 sorts before +1) prevents counting a room that just freed as still occupied.

Interval DP teaser

Not all interval problems are solved with sorting and greedy. Some require dynamic programming over sub-intervals:

• Burst Balloons (LC 312): pick the last balloon to burst in each sub-range. dp[i][j] = max coins from bursting all balloons between i and j.
• Strange Printer (LC 664): minimum turns to print a string, thinking of each turn as painting an interval.
• Matrix Chain Multiplication: classic 2D DP where you split an interval at every possible point.

The signature for interval DP problems: “divide a range into sub-ranges and combine results.” These appear at the hardest difficulty in FAANG loops.

Complexity reference

Common mistakes:

• Forgetting to sort before scanning — interval problems fall apart without sorted order.
• Sorting by start when the problem needs sorting by end (LC 435, LC 452).
• Using strict < instead of <= in the overlap check — adjacent intervals [1,2] and [2,3] typically should merge.