Interval Problems
Think of a shared calendar app trying to figure out how many meeting rooms a company needs, or a delivery app merging overlapping time slots for a driver. Interval problems, merging, inserting, scheduling, show up constantly because real systems deal in time ranges: calendar bookings, resource allocation, CPU scheduling. The whole category collapses to one insight: sort first, then a single linear pass. This lesson covers the sort-key decision and applies it across four problems.
Sorting intervals by start or end
Almost every interval problem begins with a sort, and which field you sort by is the single most important decision. Get it wrong and no amount of clever logic afterward fixes it.
- Sort by start time when merging overlaps or inserting a new interval. You need to process intervals in the order they begin to correctly detect chains of overlap.
- Sort by end time when doing interval scheduling or selection (maximize non-overlapping intervals, minimum "arrows" to cover ranges). Greedily picking the interval that finishes earliest leaves the most room for future choices.
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
by_start = sorted(intervals, key=lambda x: x[0])
by_end = sorted(intervals, key=lambda x: x[1])Why this matters so much: the correctness of the whole single-pass algorithm that follows depends on the sort setting up the right invariant. For example, once you've sorted by start and moved past an interval, you know nothing later can start before it did.
Remember: merging and inserting sort by start. Scheduling and selection sort by end. Pick the wrong one and the bug hides in code that still looks reasonable.
Merging overlapping intervals
Once sorted by start, merging is a single linear pass: keep a "current merged interval," and for each next interval, either fold it in if it overlaps, or close out the current one and start a new one.
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end: # overlaps (or touches) the last merged interval
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return mergedThe overlap check that trips people up: start <= last_end, not start < last_end. Intervals [1, 3] and [3, 5] count as overlapping (touching) in most problem statements, and merge into [1, 5]. Always check the problem statement for whether touching endpoints count as overlapping.
Remember: once sorted by start, one pass is enough. The only question at each step is whether the new interval touches or overlaps the one you're currently building.
Scheduling problems
Scheduling and selection problems ask "how many intervals can you fit without overlap," or the flip side, "how many do you need to remove." The greedy strategy: sort by end time, then greedily keep any interval whose start is at least the end of the last kept interval.
def max_non_overlapping(intervals: list[list[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # sort by END time
count = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
count += 1
last_end = end
return countWhy "sort by end, pick the earliest-ending" is optimal: the interval that finishes earliest leaves the most remaining room for future intervals. This is a classic exchange-argument greedy proof: any optimal solution can be rearranged to include the earliest-ending interval without becoming worse, and it's worth stating that justification out loud in an interview.
Remember: the interval that ends soonest leaves the most room behind it. That's why scheduling problems sort by end, not by start.
Merge Intervals
LeetCode 56 — Intervals
Intuition: Direct application of the merging pattern above: sort by start, sweep once, fold overlapping intervals together.
Approach: Sort by start time. Keep a result list; compare each interval's start against the last merged interval's end.
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or interval[0] > merged[-1][1]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return mergedComplexity: Time O(n log n) for the sort (the pass itself is O(n)), space O(n) for the output.
Common mistakes: using >= instead of > for the "no overlap" branch, an off-by-one on the touching-endpoints rule; verify against the problem's stated examples. Also, mutating the input list's inner lists when the interviewer expects the original untouched: build fresh [start, end] pairs if that matters.
Remember: Merge Intervals is the concept section's algorithm applied directly, with no extra wrinkle.
Insert Interval
LeetCode 57 — Intervals
Intuition: The input is already sorted and non-overlapping; you're inserting one new interval and merging only where it collides. Three phases: intervals entirely before the new one (copy as-is), intervals overlapping the new one (merge into it), intervals entirely after (copy as-is).
Approach: Walk the list once. Append intervals that end before the new interval starts. Merge all intervals that overlap the new interval, expanding its bounds. Append the merged interval, then append everything remaining.
def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
result = []
i, n = 0, len(intervals)
new_start, new_end = newInterval
while i < n and intervals[i][1] < new_start:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new_end:
new_start = min(new_start, intervals[i][0])
new_end = max(new_end, intervals[i][1])
i += 1
result.append([new_start, new_end])
while i < n:
result.append(intervals[i])
i += 1
return resultComplexity: Time O(n): no sort needed since the input is already sorted. Space O(n) for the output.
Common mistakes: sorting the input unnecessarily. It's guaranteed pre-sorted, so sorting wastes O(n log n) work and can hide a bug in the merge logic. Also, using < instead of <= in the overlap-detection loop, which misses touching intervals that should merge.
Remember: the input is already sorted, so don't sort it again. Just walk it once: before, overlapping, after.
Meeting Rooms
LeetCode 252 — Intervals
Intuition: Can one person attend all meetings? That's the same question as: do any two intervals overlap? Sort by start time; if any interval starts before the previous one ends, there's a conflict.
Approach: Sort by start. Single pass comparing each interval's start against the previous interval's end.
def canAttendMeetings(intervals: list[list[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
return False
return TrueComplexity: Time O(n log n), space O(1) extra (ignoring sort space).
Common mistakes: confusing this with Meeting Rooms II below, and building a heap when a simple sorted pass is enough. This variant only asks a yes/no question, not "how many rooms."
Meeting Rooms II (the natural follow-up, LeetCode 253, referenced constantly in interviews even where it's paywalled) asks for the minimum number of rooms needed, which requires tracking how many meetings are active at once. The Greedy Algorithms lesson's Meeting Rooms II walkthrough covers this in full: sort by start, track occupied rooms' end times in a min-heap, and reuse a room the moment its meeting has ended.
Remember: "can one person attend everything" is just "do any two intervals overlap." Sort by start and check neighbors.
Minimum Number of Arrows to Burst Balloons
LeetCode 452 — Intervals
Intuition: An arrow shot at position x bursts every balloon whose interval contains x. Minimizing arrows means maximizing how many balloons one arrow can burst at once, which is the same "sort by end time, greedily group overlapping intervals" scheduling pattern from earlier in this lesson, just phrased as balloons instead of meetings.
Approach: Sort by end coordinate. Shoot an arrow at the end of the first, earliest-ending, balloon's range; any later balloon whose start is <= that arrow position is burst by the same arrow. When a balloon starts after the current arrow position, you need a new arrow.
def findMinArrowShots(points: list[list[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
arrow_pos = points[0][1]
for start, end in points[1:]:
if start > arrow_pos:
arrows += 1
arrow_pos = end
return arrowsComplexity: Time O(n log n) for the sort, space O(1) extra.
Common mistakes: sorting by start instead of end, exactly the "wrong sort key" trap the concept section warns about, which produces a wrong greedy result here. Also, using >= instead of > in the new-arrow check: touching balloons, like [1,2] and [2,3], can share one arrow at position 2, so verify against the problem's boundary convention.
Remember: minimizing arrows and maximizing non-overlapping meetings are the same problem wearing different names, sort by end and greedily group.
Four problems, one recurring choice: sort by start or sort by end. Get that call right and each algorithm above becomes a few lines of linear-pass bookkeeping. Get it wrong and the bug hides in code that passes small examples and fails on edge cases, so when a new interval problem shows up, decide the sort key before writing anything else.