Intervals
Overview
Intervals are problems involving ranges of values, typically represented as [start, end] pairs, requiring operations like merging overlapping ranges, finding intersections, or scheduling non-overlapping events.
Key Properties
- Time Complexity: O(n log n) for sorting + O(n) for processing = O(n log n) overall
- Space Complexity: O(1) to O(n) depending on output requirements
- Core Idea: Sort intervals by start time, then process linearly to handle overlaps
- When to Use: Problems involving ranges, scheduling, calendar management, resource allocation
Core Algorithm Steps
- Sort intervals by start time (occasionally by end time for greedy problems)
- Process sequentially to identify overlaps or non-overlaps
- Apply merge/remove strategy based on problem requirements
- Handle edge cases like empty intervals or single intervals
When to Use Interval Algorithms
- Merge overlapping ranges: Calendar conflicts, memory allocation
- Scheduling optimization: Meeting rooms, task assignment
- Range queries: Time series data, genomic sequences
- Resource management: Bandwidth allocation, CPU scheduling
References
1) Problem Categories
Pattern 1: Interval Merging
- Description: Combine overlapping intervals into single merged intervals
- Examples: LC 56 (Merge Intervals), LC 57 (Insert Interval)
- Recognition: “Merge”, “combine”, “overlapping intervals”
- Sorting: By start time (ascending)
Pattern 2: Interval Scheduling (Greedy)
- Description: Find maximum non-overlapping intervals or minimum intervals to remove
- Examples: LC 435 (Non-overlapping Intervals), LC 452 (Minimum Arrows)
- Recognition: “Maximum”, “minimum”, “non-overlapping”, “remove”
- Sorting: By end time (ascending) for greedy approach
Pattern 3: Interval Intersection
- Description: Find common time slots or overlapping regions between interval lists
- Examples: LC 986 (Interval List Intersections), LC 1288 (Remove Covered Intervals)
- Recognition: “Intersection”, “overlap”, “common”, “covered”
- Sorting: By start time, process two pointers
Pattern 4: Interval Point Coverage
- Description: Determine points that can cover multiple intervals or find gaps
- Examples: LC 452 (Minimum Arrows), LC 1024 (Video Stitching)
- Recognition: “Cover”, “points”, “arrows”, “minimum coverage”
- Sorting: By start or end time depending on strategy
Pattern 5: Meeting Room Scheduling
- Description: Determine meeting room requirements or check scheduling conflicts
- Examples: LC 252 (Meeting Rooms), LC 253 (Meeting Rooms II)
- Recognition: “Meeting”, “conference”, “rooms”, “schedule conflicts”
- Sorting: By start time, use priority queue for room management
Pattern 6: Calendar and Booking
- Description: Handle calendar bookings with conflict detection and resolution
- Examples: LC 729 (My Calendar I), LC 731 (My Calendar II), LC 732 (My Calendar III)
- Recognition: “Calendar”, “booking”, “double booking”, “k-booking”
- Sorting: Maintain sorted intervals, binary search for insertion
2) Templates & Algorithms
Template Comparison Table
| Template Type |
Use Case |
Sorting Strategy |
When to Use |
| Merge Template |
Combine overlapping intervals |
Sort by start time |
LC 56, 57, merging problems |
| Greedy Template |
Maximum non-overlapping |
Sort by end time |
LC 435, 452, scheduling optimization |
| Two Pointer Template |
Intersection/comparison |
Sort both lists by start |
LC 986, comparing interval lists |
| Priority Queue Template |
Resource management |
Sort by start, heap by end |
LC 253, meeting room problems |
| Binary Search Template |
Calendar/booking |
Maintain sorted order |
LC 729-732, dynamic interval insertion |
Universal Interval Template
def solve_interval_problem(intervals):
"""
Universal template for interval problems
"""
# Step 1: Handle edge cases
if not intervals or len(intervals) <= 1:
return intervals
# Step 2: Sort intervals (by start time or end time based on problem)
intervals.sort(key=lambda x: x[0]) # Sort by start time
# intervals.sort(key=lambda x: x[1]) # Sort by end time for greedy problems
# Step 3: Initialize result
result = []
# Step 4: Process intervals sequentially
for current in intervals:
# Step 5: Check overlap condition with last processed interval
if not result or no_overlap_condition(result[-1], current):
result.append(current)
else:
# Step 6: Handle overlap (merge, count, or remove)
handle_overlap(result, current)
return result
def no_overlap_condition(prev, curr):
"""Check if two intervals don't overlap"""
return prev[1] < curr[0] # prev ends before curr starts
def handle_overlap(result, current):
"""Handle overlapping intervals based on problem type"""
# For merging: extend the last interval
result[-1][1] = max(result[-1][1], current[1])
# For counting: increment counter
# For removal: choose which interval to keep
Specific Templates
Template 1: Interval Merging (LC 56, 57)
def merge_intervals(intervals):
"""
Merge overlapping intervals
Time: O(n log n), Space: O(n)
"""
if not intervals:
return []
# Sort by start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
# No overlap: add current interval
if last[1] < current[0]:
merged.append(current)
# Overlap: merge intervals
else:
last[1] = max(last[1], current[1])
return merged
# Java version
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] current : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < current[0]) {
merged.add(current);
} else {
merged.get(merged.size() - 1)[1] = Math.max(
merged.get(merged.size() - 1)[1], current[1]
);
}
}
return merged.toArray(new int[merged.size()][]);
}
Template 2: Greedy Scheduling (LC 435, 452)
def min_intervals_to_remove(intervals):
"""
Find minimum intervals to remove for non-overlapping set
Time: O(n log n), Space: O(1)
"""
if not intervals:
return 0
# Sort by end time (greedy strategy)
intervals.sort(key=lambda x: x[1])
count = 0
prev_end = intervals[0][1]
for i in range(1, len(intervals)):
# Overlap detected
if intervals[i][0] < prev_end:
count += 1 # Remove current interval
else:
prev_end = intervals[i][1] # Update end time
return count
# Java version
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length <= 1) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int count = 0;
int prevEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < prevEnd) {
count++;
} else {
prevEnd = intervals[i][1];
}
}
return count;
}
Template 3: Two Pointer Intersection (LC 986)
def interval_intersection(firstList, secondList):
"""
Find intersection of two interval lists
Time: O(m + n), Space: O(min(m, n))
"""
result = []
i = j = 0
while i < len(firstList) and j < len(secondList):
# Find intersection
start = max(firstList[i][0], secondList[j][0])
end = min(firstList[i][1], secondList[j][1])
# Valid intersection
if start <= end:
result.append([start, end])
# Move pointer of interval that ends first
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return result
Template 4: Meeting Rooms with Priority Queue (LC 253)
import heapq
def min_meeting_rooms(intervals):
"""
Find minimum meeting rooms required
Time: O(n log n), Space: O(n)
"""
if not intervals:
return 0
# Sort by start time
intervals.sort(key=lambda x: x[0])
# Min heap to track end times
heap = []
for start, end in intervals:
# If earliest meeting ends before current starts
if heap and heap[0] <= start:
heapq.heappop(heap)
# Add current meeting's end time
heapq.heappush(heap, end)
return len(heap)
# Java version
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int[] interval : intervals) {
if (!heap.isEmpty() && heap.peek() <= interval[0]) {
heap.poll();
}
heap.offer(interval[1]);
}
return heap.size();
}
Template 5: Calendar Booking (LC 729)
class MyCalendar:
"""
Calendar with overlap detection using binary search
Time: O(log n) per booking, Space: O(n)
"""
def __init__(self):
self.bookings = []
def book(self, start, end):
# Binary search for insertion position
left, right = 0, len(self.bookings)
while left < right:
mid = (left + right) // 2
if self.bookings[mid][1] <= start:
left = mid + 1
else:
right = mid
# Check overlap with neighbors
if left > 0 and self.bookings[left - 1][1] > start:
return False
if left < len(self.bookings) and self.bookings[left][0] < end:
return False
# No overlap, insert booking
self.bookings.insert(left, [start, end])
return True
3) Problems by Pattern
Merging Pattern Problems
| Problem |
LC # |
Key Technique |
Difficulty |
Template |
| Merge Intervals |
56 |
Sort by start, merge overlaps |
Medium |
Merge Template |
| Insert Interval |
57 |
Insert and merge |
Medium |
Merge Template |
| Summary Ranges |
228 |
Consecutive number ranges |
Easy |
Merge Template |
| Data Stream as Disjoint Intervals |
352 |
TreeMap/SortedDict |
Hard |
Merge Template |
| Merge Similar Items |
2363 |
Merge by weight |
Easy |
Merge Template |
Greedy Scheduling Problems
| Problem |
LC # |
Key Technique |
Difficulty |
Template |
| Non-overlapping Intervals |
435 |
Sort by end, greedy removal |
Medium |
Greedy Template |
| Minimum Arrows to Burst Balloons |
452 |
Sort by end, count arrows |
Medium |
Greedy Template |
| Maximum Length of Pair Chain |
646 |
Sort by second element |
Medium |
Greedy Template |
| Activity Selection Problem |
- |
Classic greedy algorithm |
Medium |
Greedy Template |
| Car Pooling |
1094 |
Timeline + capacity |
Medium |
Greedy Template |
Intersection & Coverage Problems
| Problem |
LC # |
Key Technique |
Difficulty |
Template |
| Interval List Intersections |
986 |
Two pointers |
Medium |
Two Pointer Template |
| Remove Covered Intervals |
1288 |
Sort and filter |
Medium |
Merge Template |
| Find Right Interval |
436 |
Binary search |
Medium |
Binary Search |
| Employee Free Time |
759 |
Merge + find gaps |
Hard |
Merge Template |
| Video Stitching |
1024 |
Greedy coverage |
Medium |
Greedy Template |
Meeting Room & Scheduling Problems
| Problem |
LC # |
Key Technique |
Difficulty |
Template |
| Meeting Rooms |
252 |
Sort and check conflicts |
Easy |
Basic Template |
| Meeting Rooms II |
253 |
Priority queue |
Medium |
Priority Queue Template |
| Meeting Scheduler |
1229 |
Two pointers + duration |
Medium |
Two Pointer Template |
| Minimum Time to Make Rope Colorful |
1578 |
Consecutive intervals |
Medium |
Greedy Template |
| Course Schedule III |
630 |
Priority queue + greedy |
Hard |
Priority Queue Template |
Calendar & Booking Problems
| Problem |
LC # |
Key Technique |
Difficulty |
Template |
| My Calendar I |
729 |
Sorted list + binary search |
Medium |
Calendar Template |
| My Calendar II |
731 |
Double booking detection |
Medium |
Calendar Template |
| My Calendar III |
732 |
K-booking with timeline |
Hard |
Calendar Template |
| Exam Room |
855 |
Max gap maintenance |
Medium |
Binary Search |
| Range Module |
715 |
Segment tree/intervals |
Hard |
Advanced Template |
Advanced Interval Problems
| Problem |
LC # |
Key Technique |
Difficulty |
Template |
| Falling Squares |
699 |
Coordinate compression |
Hard |
Advanced Template |
| The Skyline Problem |
218 |
Sweep line + priority queue |
Hard |
Advanced Template |
| Rectangle Area II |
850 |
Coordinate compression |
Hard |
Advanced Template |
| Perfect Rectangle |
391 |
Area calculation + validation |
Hard |
Advanced Template |
| Count Integers in Intervals |
2276 |
Dynamic intervals |
Hard |
Advanced Template |
4) Pattern Selection Strategy
Decision Framework Flowchart
Problem Analysis for Interval Problems:
1. Are you merging overlapping intervals?
├── YES → Use Merge Template (LC 56, 57)
│ ├── Single interval insertion? → Insert Interval Template
│ └── Multiple overlaps? → Standard Merge Template
└── NO → Continue to 2
2. Are you finding maximum non-overlapping intervals?
├── YES → Use Greedy Template (LC 435, 452)
│ ├── Sort by end time
│ └── Greedy selection strategy
└── NO → Continue to 3
3. Are you finding intersections between interval lists?
├── YES → Use Two Pointer Template (LC 986)
│ ├── Two sorted lists? → Standard Two Pointer
│ └── Multiple lists? → Merge then process
└── NO → Continue to 4
4. Are you managing meeting rooms or resources?
├── YES → Use Priority Queue Template (LC 253)
│ ├── Count resources needed? → Min heap approach
│ └── Check availability? → Sort + scan
└── NO → Continue to 5
5. Are you handling dynamic bookings/calendar?
├── YES → Use Calendar Template (LC 729-732)
│ ├── Single booking? → Binary search insertion
│ ├── Double booking allowed? → Two lists approach
│ └── K-booking? → Timeline/sweep line
└── NO → Consider Advanced Templates
6. Advanced cases (Skyline, Rectangles, etc.)
├── Coordinate compression needed?
├── Sweep line algorithm required?
└── Segment tree for range operations?
Template Selection Guide
Quick Decision Tree:
- Overlap Detection:
prev[1] >= curr[0] (assuming sorted by start)
- Merge Strategy: Extend
prev[1] = max(prev[1], curr[1])
- Greedy Strategy: Sort by end time, keep earliest ending
- Resource Management: Use min heap for end times
- Dynamic Insertion: Maintain sorted order with binary search
5) Key Patterns & Overlap Detection
Overlap Detection Methods
Method 1: After Sorting by Start Time
def has_overlap(interval1, interval2):
"""Check if two intervals overlap (sorted by start)"""
return interval1[1] > interval2[0]
Method 2: General Case (Any Order)
def has_overlap(interval1, interval2):
"""Check if two intervals overlap (any order)"""
start1, end1 = interval1
start2, end2 = interval2
return start1 < end2 and start2 < end1
Overlap Visualization
Case 1 - No Overlap:
|----| interval1
|----| interval2
Case 2 - Overlap:
|-------|
|-------|
Case 3 - Complete Overlap:
|-----------|
|-----|
Common Interval Operations
def merge_two_intervals(a, b):
"""Merge two overlapping intervals"""
return [min(a[0], b[0]), max(a[1], b[1])]
def interval_length(interval):
"""Calculate interval length"""
return interval[1] - interval[0]
def intervals_intersection(a, b):
"""Find intersection of two intervals"""
start = max(a[0], b[0])
end = min(a[1], b[1])
return [start, end] if start <= end else None
def point_in_interval(point, interval):
"""Check if point is in interval"""
return interval[0] <= point <= interval[1]
6) Summary & Quick Reference
Complexity Quick Reference
| Operation |
Time |
Space |
Notes |
| Sort intervals |
O(n log n) |
O(1) |
Essential first step |
| Merge overlapping |
O(n) |
O(n) |
After sorting |
| Find intersections |
O(m + n) |
O(min(m,n)) |
Two pointer approach |
| Meeting rooms |
O(n log n) |
O(n) |
Priority queue for end times |
| Calendar booking |
O(log n) |
O(n) |
Binary search per insertion |
| Greedy scheduling |
O(n log n) |
O(1) |
Sort by end time |
Template Quick Reference
| Template |
Pattern |
Key Code |
| Merge |
Overlapping intervals |
if last[1] < curr[0]: append else: merge |
| Greedy |
Non-overlapping max |
sort(key=end); if curr[0] >= prev[1]: count++ |
| Two Pointer |
List intersection |
start=max(starts), end=min(ends) |
| Priority Queue |
Resource management |
heappush(end_time); if heap[0] <= start: heappop |
| Binary Search |
Dynamic insertion |
bisect.insort or custom binary search |
Common Patterns & Tricks
Pattern 1: Merge Overlapping
# Standard merging after sorting
intervals.sort()
merged = [intervals[0]]
for curr in intervals[1:]:
if merged[-1][1] < curr[0]:
merged.append(curr)
else:
merged[-1][1] = max(merged[-1][1], curr[1])
Pattern 2: Greedy Selection
# Sort by end time for optimal selection
intervals.sort(key=lambda x: x[1])
count = 1
prev_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= prev_end:
count += 1
prev_end = end
Pattern 3: Timeline Events
# Convert intervals to events for sweep line
events = []
for start, end in intervals:
events.append((start, 1)) # start event
events.append((end, -1)) # end event
events.sort()
Problem-Solving Steps
- Identify Pattern: Merging, scheduling, intersection, or resource management?
- Choose Sorting Strategy: By start time (merging) or end time (greedy)
- Select Template: Use appropriate template from above
- Handle Edge Cases: Empty arrays, single intervals, identical intervals
- Optimize: Consider space optimization for large datasets
Common Mistakes & Tips
🚫 Common Mistakes:
- Wrong sorting order: Sorting by start when should sort by end (greedy problems)
- Off-by-one errors: Using
<= vs < in overlap conditions
- Edge case handling: Not checking empty arrays or single intervals
- Merge logic errors: Forgetting to update both start and end during merge
- Greedy strategy confusion: Not understanding why sorting by end time works
- Space complexity: Creating unnecessary intermediate data structures
✅ Best Practices:
- Always sort first: Most interval problems require sorted input
- Clear overlap definition: Define overlap condition clearly before coding
- Use appropriate template: Match template to problem pattern
- Test edge cases: Empty input, single interval, identical intervals
- Visualize examples: Draw intervals to understand overlap patterns
- Choose right sorting key: Start time for merging, end time for greedy
Interview Tips
- Start with examples: Draw intervals on paper to visualize
- Clarify edge cases: What about empty intervals? Point intervals?
- Explain sorting choice: Why sorting by start/end time?
- Walk through algorithm: Show merge/greedy logic step by step
- Optimize incrementally: Start with working solution, then optimize
- Practice common patterns: Master the 5 main templates above
- Time complexity analysis: Always explain O(n log n) sorting + O(n) processing
Data Structure Conversion Tricks
List to Array (Java)
List<int[]> result = new ArrayList<>();
// ... populate result
return result.toArray(new int[result.size()][]);
Efficient Merging in Python
# Using list comprehension for functional style
def merge_intervals(intervals):
intervals.sort()
result = [intervals[0]]
[result.append(curr) if result[-1][1] < curr[0]
else result[-1].__setitem__(1, max(result[-1][1], curr[1]))
for curr in intervals[1:]]
return result
- Greedy Algorithms: Interval scheduling optimization
- Binary Search: Calendar booking and insertion problems
- Priority Queue: Meeting room and resource management
- Two Pointers: Intersection and comparison problems
- Sweep Line: Advanced problems like skyline and rectangles
- Segment Trees: Range updates and queries on intervals