10.1 Intervals (Sorting, Merging & Sweep Line)

1. What Is an Interval?

An Interval [start, end] is simply a pair of numbers representing a continuous span on a timeline — such as a calendar meeting from 1:00 to 4:00 ([1, 4]), a flight reservation, or a project schedule.

2. Why Do We Need Interval Sorting & How Does Overlap Work?

The Pain of Unsorted Intervals (O(N^2))

If someone gives you 10,000 meetings in random order and asks which meetings conflict, you would have to compare every meeting against every other meeting (O(N^2)).

How Sorting Unlocks a Single O(N) Pass

The moment you sort the intervals (O(N log N)), any overlapping intervals are guaranteed to sit right next to each other!

There are only two sorting strategies you need to know:

1. Sort by start time (intervals.sort(key=lambda x: x[0])): Use this when merging or inserting intervals (Merge Intervals, Insert Interval). Once a = [s1, e1] comes before b = [s2, e2] (s1 <= s2), they overlap if and only if s2 <= e1 (the second interval starts before the first one finishes). Merge them into [s1, max(e1, e2)]!
2. Sort by end time (intervals.sort(key=lambda x: x[1])): Use this when choosing the maximum number of non-overlapping intervals (Non-overlapping Intervals). Why? Because keeping the meeting that finishes earliest frees up your room as soon as possible for future meetings!

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Merge Overlapping Intervals (Sort by START time) -> O(N log N)
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
  intervals.sort(key=lambda x: x[0])
  merged = [intervals[0]]
  for start, end in intervals[1:]:
      if start <= merged[-1][1]:  # Overlaps with previous interval!
          merged[-1][1] = max(merged[-1][1], end)
      else:
          merged.append([start, end])
  return merged

# 2. Minimum Removals to Eliminate Overlaps (Sort by END time) -> O(N log N)
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
  intervals.sort(key=lambda x: x[1])
  removed = 0
  prev_end = intervals[0][1]
  for start, end in intervals[1:]:
      if start < prev_end:
          removed += 1      # Conflict! Drop the later-ending meeting
      else:
          prev_end = end
  return removed

4. Core Interview Patterns & Common Traps

res = []
i, n = 0, len(intervals)
# 1. Add all intervals that end strictly before newInterval starts
while i < n and intervals[i][1] < newInterval[0]:
  res.append(intervals[i]); i += 1
# 2. Merge all intervals that start before or at newInterval's end
while i < n and intervals[i][0] <= newInterval[1]:
  newInterval[0] = min(newInterval[0], intervals[i][0])
  newInterval[1] = max(newInterval[1], intervals[i][1])
  i += 1
res.append(newInterval)
# 3. Append the remaining intervals
return res + intervals[i:]

5. Practice On Your Own (Curated Submodule Problems)