Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Intervals

Interval problems reduce to sorting plus one sweep. Learn the overlap test (and closed vs half-open), when to sort by start versus end, and how sweep lines and min-heaps count overlaps, with Merge Intervals, Non-overlapping Intervals and Meeting Rooms II animated step by step.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 9 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

The overlap test and closed vs half-open intervals
Merge by start, greedy selection by end
Sweep lines and min-heaps for maximum overlap
Six LeetCode problems with animated walkthroughs

📚 Before you start

Part 1The Pattern

Interval problems (meetings, bookings, time ranges, genome segments) almost always start the same way: sort by start time, then sweep left to right while comparing each interval with the last one you kept. Sorting costs O(n log n) and the sweep is O(n). Two related tools cover the rest: sorting by end time for greedy selection, and a sweep line over events (or a min-heap of end times) for "how many overlap at once".

Sorted intervals merged left to right when they overlap

1The Overlap Test

Two intervals a = [a0, a1] and b = [b0, b1] overlap when each starts before the other ends:

text

closed  [s, e]:  a0 <= b1 and b0 <= a1      ([1,4] and [4,5] overlap)
half-open [s, e): a0 <  b1 and b0 <  a1      (meetings 9–10 and 10–11 don't conflict)

Always ask which convention the problem uses: "does a meeting ending at 10:00 conflict with one starting at 10:00?" The answer changes < into <=.

After sorting by start, you only need to compare with the last merged interval: start <= last.end.

2Templates

typescript

function mergeIntervals(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else merged.push([start, end]);
  }
  return merged;
}

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

python

def merge_intervals(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[0])     # 1. sort by start
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:                # 2. overlaps the last one?
            merged[-1][1] = max(merged[-1][1], end)          #    extend it
        else:
            merged.append([start, end])                      #    or start a new one
    return merged

def overlaps(a, b):
    return a[0] < b[1] and b[0] < a[1]                      # half-open [start, end)

3Three Strategies

Question	Strategy	Example
Merge / union of ranges	sort by start, extend the last	Merge Intervals, Insert Interval
Keep as many non-overlapping as possible / remove the fewest	sort by end, greedily keep the earliest-finishing	Non-overlapping Intervals, arrows
How many overlap at the same time (rooms, servers, peak load)	sweep line over +1/−1 events, or a min-heap of end times	Meeting Rooms II, car pooling

Why sort by end for greedy selection? The interval that finishes first leaves the most room for everything after it. Any optimal solution can swap its first interval for the earliest-finishing one without losing anything (an exchange argument), so the greedy choice is always safe.

4Sweep Line

Turn each interval into two events, (start, +1) and (end, −1), sort them (processing −1 before +1 at equal times for half-open intervals), and keep a running count. The maximum running count is the maximum overlap. It generalizes to weighted loads (+passengers, −passengers) and is the core of calendar and capacity problems.

Under the HoodInterval Trees▾

When intervals arrive dynamically and you must answer "which intervals overlap x?" many times, sorting once isn't enough. An interval tree (or a segment tree over coordinates) stores intervals in a balanced BST keyed by start, each node annotated with the maximum end in its subtree, giving O(log n + k) queries. Databases use similar ideas for range indexes (PostgreSQL's GiST indexes on tsrange), and calendars use them for conflict checks. In interviews, mentioning this as the follow-up for "what if intervals keep arriving?" is a strong senior signal.

⚠️ Common Pitfalls

Not sorting first, or sorting by the wrong key (start vs end).
Closed vs half-open confusion: [1,2] and [2,3] merge if closed, not if half-open.
Forgetting max when extending: [1,10] followed by [2,3] must stay [1,10].
Mutating the input when the caller expects it unchanged (sort a copy).
Event order at equal times in sweep lines: decide whether an end and a start at the same time overlap.

📋 Quick Reference

text

Merge: sort by start; if s <= last.end: last.end = max(last.end, e) else push
Greedy keep max non-overlapping: sort by end; keep if s >= lastEnd
Max overlap: events (s,+1),(e,-1); sort; running max   (or min-heap of ends)
O(n log n) for the sort, O(n) sweep

Part 2Interview Problems

Six problems covering the three strategies: merge by start, greedy by end, and counting overlaps with a heap or sweep line.

1Merge Intervals (LeetCode 56)

🟠 Medium. Merge all overlapping intervals and return the non-overlapping result.

text

[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

Approach. Sort by start. Walk the intervals: if the current one starts before (or at) the end of the last merged interval, extend that interval's end; otherwise start a new one.

Complexity. O(n log n) time for sorting, O(n) for the output.

typescript

function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [s, e] of sorted) {
    const last = merged[merged.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else merged.push([s, e]);
  }
  return merged;
}

python

def merge(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[0])
    merged = []
    for s, e in intervals:
        if merged and s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged

2Insert Interval (LeetCode 57)

🟠 Medium. intervals is sorted and non-overlapping. Insert newInterval, merging where needed.

text

[[1,2],[3,5],[6,7],[8,10],[12,16]] + [4,8] → [[1,2],[3,10],[12,16]]

Approach. Three phases in one pass: copy intervals that end before the new one starts; merge every interval that overlaps it (expand the new interval's start/end); copy the rest. No sort needed: O(n).

Complexity. O(n) time.

typescript

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const res: number[][] = [];
  let i = 0;
  let [s, e] = newInterval;
  while (i < intervals.length && intervals[i][1] < s) res.push(intervals[i++]);
  while (i < intervals.length && intervals[i][0] <= e) {
    s = Math.min(s, intervals[i][0]);
    e = Math.max(e, intervals[i][1]);
    i++;
  }
  res.push([s, e]);
  while (i < intervals.length) res.push(intervals[i++]);
  return res;
}

python

def insert(intervals, new):
    res, i, n = [], 0, len(intervals)
    s, e = new
    while i < n and intervals[i][1] < s:          # entirely before
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= e:         # overlapping: absorb
        s, e = min(s, intervals[i][0]), max(e, intervals[i][1]); i += 1
    res.append([s, e])
    res.extend(intervals[i:])                     # entirely after
    return res

3Non-overlapping Intervals (LeetCode 435)

🟠 Medium. Return the minimum number of intervals to remove so that the rest don't overlap (touching endpoints are fine).

text

[[1,2],[2,3],[3,4],[1,3]] → 1   (remove [1,3])

Approach. Equivalent to keeping the maximum number of non-overlapping intervals. Sort by end; keep an interval if it starts at or after the end of the last kept one, otherwise remove it. Earliest-finishing first leaves the most room.

Complexity. O(n log n) time, O(1) extra space.

typescript

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let removed = 0, lastEnd = -Infinity;
  for (const [s, e] of sorted) {
    if (s >= lastEnd) lastEnd = e; else removed++;
  }
  return removed;
}

python

def erase_overlap_intervals(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[1])
    removed, last_end = 0, float("-inf")
    for s, e in intervals:
        if s >= last_end:
            last_end = e            # keep it
        else:
            removed += 1            # overlaps the kept one → remove
    return removed

4Meeting Rooms (LeetCode 252)

🟢 Easy. Can one person attend all meetings? (Intervals are half-open: a meeting ending at 10 doesn't conflict with one starting at 10.)

text

[[0,30],[5,10],[15,20]] → false

Approach. Sort by start; any meeting that starts before the previous one ends is a conflict.

Complexity. O(n log n) time.

typescript

function canAttendMeetings(intervals: number[][]): boolean {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < sorted.length; i++) if (sorted[i][0] < sorted[i - 1][1]) return false;
  return true;
}

python

def can_attend_meetings(intervals):
    intervals = sorted(intervals)
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True

5Meeting Rooms II (LeetCode 253)

🟠 Medium. Return the minimum number of conference rooms needed for all meetings (half-open intervals).

text

[[0,30],[5,10],[15,20]] → 2

Approach. Sort meetings by start and keep a min-heap of end times of rooms in use. For each meeting, if the earliest-ending room is free by its start, reuse it (pop); then push this meeting's end. The heap size is the number of rooms. (Equivalent: sweep over +1/−1 events and take the peak.)

Complexity. O(n log n) time, O(n) space.

typescript

function minMeetingRooms(intervals: number[][]): number {
  // sweep line: starts and ends sorted separately
  const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);
  const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);
  let rooms = 0, best = 0, j = 0;
  for (let i = 0; i < starts.length; i++) {
    while (j < ends.length && ends[j] <= starts[i]) { rooms--; j++; }   // free rooms first
    rooms++;
    best = Math.max(best, rooms);
  }
  return best;
}

python

import heapq

def min_meeting_rooms(intervals):
    ends = []                                   # end times of rooms in use
    for s, e in sorted(intervals):
        if ends and ends[0] <= s:
            heapq.heappop(ends)                 # that room is free again
        heapq.heappush(ends, e)
    return len(ends)

6Minimum Number of Arrows to Burst Balloons (LeetCode 452)

🟠 Medium. Balloons span [xstart, xend] (closed). An arrow at x bursts every balloon containing x. Return the minimum number of arrows.

text

[[10,16],[2,8],[1,6],[7,12]] → 2   (arrows at 6 and 12)

Approach. Sort by end. Shoot the first arrow at the first balloon's end; it bursts every balloon starting at or before that point. When a balloon starts after the current arrow, shoot a new arrow at its end.

Complexity. O(n log n) time.

typescript

function findMinArrowShots(points: number[][]): number {
  const sorted = [...points].sort((a, b) => a[1] - b[1]);
  let arrows = 0, arrowX = -Infinity;
  for (const [s, e] of sorted) {
    if (s > arrowX) { arrows++; arrowX = e; }
  }
  return arrows;
}

python

def find_min_arrow_shots(points):
    points = sorted(points, key=lambda p: p[1])
    arrows, arrow_x = 0, float("-inf")
    for s, e in points:
        if s > arrow_x:              # not hit by the current arrow
            arrows += 1
            arrow_x = e
    return arrows

🧠 Key takeaways

Two intervals overlap when each starts before the other ends; settle closed vs half-open first.
Merge by sorting on start and extending the last interval (remember max).
Greedy selection (fewest removals, arrows) sorts by end.
Max overlap (rooms) = sweep line peak, or the size of a min-heap of end times.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_intervals_exercise_1.py

TS PY

algo_intervals_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. After sorting by start, which interval do you compare the current one with when merging?

Sorted order makes that sufficient.

2. Why sort by end time for Non-overlapping Intervals?

Greedy choice is safe.

3. Meeting Rooms II: what does the heap store?

Min end = next room to free.

4. Do [1,2] and [2,3] overlap?

Ask the interviewer.

Source: algo_intervals_theory_1.md, algo_intervals_theory_2.md · generated by tools/build_lessons.py