Interval Algorithm Patterns
Interval problems appear constantly in coding interviews — at Google, Meta, Airbnb, and Uber. The key skill: recognizing the overlap condition and knowing when to sort by start vs end time. Most interval problems reduce to one of five patterns.
Overlap Detection
Two intervals [a, b] and [c, d] overlap if and only if: a < d AND c < b (open intervals). For closed intervals [a, b] and [c, d]: a <= d AND c <= b. They do NOT overlap if: b <= c OR d <= a (one ends before the other starts). This single condition is the foundation for all interval algorithms.
Pattern 1: Merge Intervals (LC 56)
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0]) # sort by start time
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps with last merged
merged[-1][1] = max(merged[-1][1], end) # extend end
else:
merged.append([start, end]) # no overlap: add new interval
return merged
Time O(n log n) for sort, O(n) for merge. The condition start <= merged[-1][1] catches both overlap and touching intervals ([1,3],[3,5] → [1,5]).
Pattern 2: Insert Interval (LC 57)
def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
result = []
i = 0
n = len(intervals)
new_start, new_end = new_interval
# Add all intervals that end before new_interval starts
while i < n and intervals[i][1] < new_start:
result.append(intervals[i])
i += 1
# Merge all overlapping intervals
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])
# Add remaining intervals
result.extend(intervals[i:])
return result
Time O(n), no sorting needed since intervals are already sorted. Three passes: before, overlap, after.
Pattern 3: Non-Overlapping Intervals — Minimum Removals (LC 435)
Greedy: sort by end time. Keep an interval if it doesn’t overlap with the previous kept interval. This is the classic “Activity Selection” problem — greedily pick intervals that end earliest to leave room for future intervals.
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # sort by END time (key insight!)
kept = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end: # no overlap with last kept interval
kept += 1
last_end = end
return len(intervals) - kept # removals = total - kept
Why sort by end? Sorting by start doesn’t work — an interval that starts first but ends very late blocks many future intervals. Ending earliest gives the most room for remaining intervals.
Pattern 4: Meeting Rooms II — Minimum Rooms (LC 253)
Find the minimum number of conference rooms required to hold all meetings.
import heapq
def min_meeting_rooms(intervals: list[list[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # sort by start time
heap = [] # min-heap of end times (rooms, by when they free up)
for start, end in intervals:
if heap and heap[0] int:
starts = sorted(s for s, _ in intervals)
ends = sorted(e for _, e in intervals)
rooms = max_rooms = 0
j = 0
for start in starts:
if start < ends[j]:
rooms += 1
else:
j += 1 # a room freed up
max_rooms = max(max_rooms, rooms)
return max_rooms
The heap approach is O(n log n). At any point, heap size = current number of rooms in use. The two-pointer approach is cleaner in interviews.
Pattern 5: Employee Free Time (LC 759)
Find all time intervals where ALL employees are free. Merge all schedules, find gaps.
def employee_free_time(schedule: list[list[list[int]]]) -> list[list[int]]:
# Flatten all intervals
all_intervals = sorted(
[interval for employee in schedule for interval in employee],
key=lambda x: x[0]
)
# Merge overlapping intervals
merged = [all_intervals[0][:]]
for start, end in all_intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
# Gaps between merged intervals are free time
free_time = []
for i in range(1, len(merged)):
free_time.append([merged[i-1][1], merged[i][0]])
return free_time
Cheat Sheet
| Problem | Sort By | Strategy |
|---|---|---|
| Merge intervals | Start time | Extend last merged interval’s end |
| Insert interval | Already sorted | 3 phases: before, merge, after |
| Min removals | End time | Greedy keep (Activity Selection) |
| Min meeting rooms | Start time | Min-heap of end times |
| Free time | Start time | Merge all, find gaps |
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the key insight for solving the Merge Intervals problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort intervals by start time first. Then iterate: for each interval, check if it overlaps with the last merged interval. Two intervals [a,b] and [c,d] overlap if c <= b (the new interval starts before the previous ends). If they overlap, extend the merged interval's end to max(b, d). If they don't overlap, start a new merged interval. The critical detail: use max(b, d) — not just d — because one interval may be completely contained inside another ([1,10] and [2,5] → [1,10], not [1,5]). Time: O(n log n) for sorting, O(n) for the merge pass. The condition c <= b (not c < b) handles touching intervals: [1,3] and [3,5] should merge to [1,5] in most problems. Read the problem to determine if touching counts as overlapping."}},{"@type":"Question","name":"How do you find the minimum number of meeting rooms required?","acceptedAnswer":{"@type":"Answer","text":"Use a min-heap of end times. Sort meetings by start time. For each meeting: if the heap is non-empty and the earliest-ending meeting (heap minimum) ends at or before the current meeting starts, that room is free — replace the heap minimum with the current meeting's end time (reuse the room). Otherwise, push the current meeting's end time (new room needed). The heap size after processing all meetings equals the minimum rooms required. Why min-heap? It gives O(1) access to the room that frees up earliest — exactly what you need to decide whether any room is available. Time: O(n log n). Alternative: sort starts and ends separately, use two pointers. For each start time: if a meeting has ended (end pointer), increment end pointer (room freed); else add a room. Maximum rooms_in_use across all starts = answer."}},{"@type":"Question","name":"Why do you sort by end time for the Non-Overlapping Intervals problem?","acceptedAnswer":{"@type":"Answer","text":"This is the classic Activity Selection problem — find the maximum number of non-overlapping intervals (equivalently, minimum intervals to remove). Greedy algorithm: sort by end time, then greedily pick each interval that doesn't overlap with the last picked. Sorting by end time is correct because intervals that end earliest leave the most time for future intervals. A counterexample for sorting by start time: intervals [[1,100],[2,3],[4,5],[6,7]]. Sorted by start: pick [1,100] first, which blocks everything else. Sorted by end: pick [2,3], [4,5], [6,7] — 3 intervals kept, only remove [1,100] (1 removal). The greedy proof: if any optimal solution skips an interval we would pick, we can swap it with ours without increasing conflicts (an interval that ends earlier or at the same time can only reduce or maintain future conflicts)."}}]}
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
🏢 Asked at: Atlassian Interview Guide
🏢 Asked at: Coinbase Interview Guide