Interval Problem Patterns: Merge, Insert, Overlap & Scheduling
Interval problems require manipulating ranges [start, end]. They appear frequently in meeting room, scheduling, and calendar problems. Sort first — almost always the right first move.
Core Insight: Sort by Start Time
Sorting intervals by start time reduces most problems from O(n²) to O(n log n). After sorting, you only need to compare adjacent intervals.
Pattern 1: Merge Intervals
Merge all overlapping intervals into the fewest non-overlapping intervals:
def merge(intervals):
intervals.sort() # sort by start time
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlap: current start <= prev end
merged[-1][1] = max(merged[-1][1], end) # extend end
else:
merged.append([start, end]) # no overlap: new interval
return merged
Pattern 2: Insert Interval
Insert a new interval into a sorted non-overlapping list, merging as needed:
def insert(intervals, new_interval):
result = []
i = 0
# Add all intervals ending before new_interval starts
while i < len(intervals) and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# Merge all overlapping intervals
while i < len(intervals) and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
result.append(new_interval)
# Add remaining intervals
result.extend(intervals[i:])
return result
Pattern 3: Meeting Rooms (Overlap Detection)
# Can attend all meetings? (no overlap)
def can_attend_meetings(intervals):
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return False
return True
# Minimum rooms needed (max concurrent meetings)
import heapq
def min_meeting_rooms(intervals):
intervals.sort()
heap = [] # end times of active meetings
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end)
else:
heapq.heappush(heap, end)
return len(heap)
Pattern 4: Non-Overlapping Intervals (Minimum Removals)
Greedy: sort by end time, keep as many non-overlapping intervals as possible, count the rest as removals:
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # sort by end time
removals = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
removals += 1 # remove (skip) this interval
return removals
Pattern 5: Interval List Intersections
Find all intersecting intervals between two sorted lists using two pointers:
def interval_intersection(A, B):
result = []
i = j = 0
while i < len(A) and j < len(B):
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi])
# Advance the pointer with earlier end
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
Pattern 6: Employee Free Time
Find free intervals across all employee schedules. Merge all into one list, then find gaps:
def employee_free_time(schedule):
all_intervals = sorted([iv for emp in schedule for iv in emp], key=lambda x: x[0])
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 consecutive merged intervals = free time
return [[merged[i][1], merged[i+1][0]] for i in range(len(merged)-1)]
Classic Interval Problems
| Problem | Algorithm | Complexity |
|---|---|---|
| Merge Intervals | Sort + linear scan | O(n log n) |
| Insert Interval | Three-phase linear scan | O(n) |
| Meeting Rooms I | Sort + compare adjacent | O(n log n) |
| Meeting Rooms II | Sort + min-heap of end times | O(n log n) |
| Non-Overlapping Intervals | Greedy by end time | O(n log n) |
| Interval Intersections | Two pointers | O(m + n) |
| Employee Free Time | Merge all + find gaps | O(n log n) |
Interview Tips
- Always clarify: are intervals inclusive or exclusive? Can they be empty ([a,a])?
- Sort by start time for merge/insert; sort by end time for greedy non-overlap selection
- The overlap condition: A overlaps B if A.start < B.end AND B.start < A.end (or <= for inclusive)
- For counting concurrent events, the difference array / sweep line technique works in O(n log n)
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you merge overlapping intervals efficiently?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Sort intervals by start time. Initialize a result list with the first interval. For each subsequent interval, compare its start to the last interval in the result. If start <= result[-1].end, there is overlap—update result[-1].end = max(result[-1].end, current.end). Otherwise, append the current interval. Time O(n log n) for sorting, O(n) for the merge pass. The key: sorting by start ensures you only need to look at the last merged interval.” }
},
{
“@type”: “Question”,
“name”: “What is the difference between Meeting Rooms I and Meeting Rooms II?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Meeting Rooms I asks: can one person attend all meetings? Solution: sort by start time, check if any interval's start < previous interval's end. If yes, there's a conflict. Meeting Rooms II asks: what is the minimum number of rooms needed? Solution: sort by start time, use a min-heap of end times for active meetings. If the earliest ending meeting ends before the next one starts, reuse the room; otherwise add a new room. Heap size at the end = minimum rooms needed.” }
},
{
“@type”: “Question”,
“name”: “How do you find the minimum number of intervals to remove to make the rest non-overlapping?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “This is equivalent to finding the maximum set of non-overlapping intervals and removing the rest. Greedy approach: sort by end time (not start time). Iterate and greedily select each interval that starts at or after the last selected end. Count unselected intervals as removals. Sorting by end time is crucial — it maximizes the intervals we keep, minimizing removals. Time O(n log n).” }
}
]
}