Intervals

Greedy & IntervalsPriority 4 of 5 — High value — a gap here costs you roundsHigh value Updated Sep 18, 2026
Section priorityPriority 5 of 5 — Must know — expect it in almost every loopMust knowPriority 4 of 5 — High value — a gap here costs you roundsHigh valuePriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowingPriority 2 of 5 — Niche — read once, revisit only if a company is known to askNicheMarked on the sections that carry it — unmarked sections are background/reference.

Scope — Sort-then-merge interval problems — merge, insert, count overlaps, minimum removals. See also: scanning_line.md — event-based sweeps when you need a running count; difference_array.md — many range updates, one final read; array_overlap_explaination.md — the overlap predicate itself; heap.md — interval scheduling with a priority queue.

LeetCode Problem Lists

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

  1. Sort intervals by start time (occasionally by end time for greedy problems)
  2. Process sequentially to identify overlaps or non-overlaps
  3. Apply merge/remove strategy based on problem requirements
  4. 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 — LC 56 Priority 5 of 5 — Must know — expect it in almost every loop

  • 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) — LC 435 Priority 4 of 5 — High value — a gap here costs you rounds

  • 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 — LC 986 Priority 3 of 5 — Worth knowing — usually a variant of a must-know pattern

  • 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 — LC 452 Priority 3 of 5 — Worth knowing — usually a variant of a must-know pattern

  • 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 — LC 253 Priority 5 of 5 — Must know — expect it in almost every loop

  • 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 — LC 729

  • 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 Priority 4 of 5 — High value — a gap here costs you rounds

python
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)

python
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
// 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)

python
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
// 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)

python
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)

python
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
// 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)

python
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
Partition Labels 763 Last-occurrence intervals + one-pass merge Medium Merge Template
Jump Game II 45 Implicit intervals + greedy cover Medium Greedy Template
Jump Game 55 Farthest-reach scan 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
Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts 1465 Max gap between sorted cuts Medium Gap Scan Template
Missing Ranges 163 Gap scan over sorted unique values Medium Gap Scan Template
Find All Numbers Disappeared in an Array II 4031 Clamp + dedupe + sort, then gap scan Medium Gap Scan 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

text
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:

  1. Overlap Detection: prev[1] >= curr[0] (assuming sorted by start)
  2. Merge Strategy: Extend prev[1] = max(prev[1], curr[1])
  3. Greedy Strategy: Sort by end time, keep earliest ending
  4. Resource Management: Use min heap for end times
  5. Dynamic Insertion: Maintain sorted order with binary search

5) Key Patterns & Overlap Detection

Overlap Detection Methods

Method 1: After Sorting by Start Time

python
def has_overlap(interval1, interval2):
    """Check if two intervals overlap (sorted by start)"""
    return interval1[1] > interval2[0]

Method 2: General Case (Any Order)

python
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

text
Case 1 - No Overlap:
|----| interval1
        |----| interval2

Case 2 - Overlap:
|-------|
    |-------|

Case 3 - Complete Overlap:
|-----------|
   |-----|

Common Interval Operations

python
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

python
# 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

python
# 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

python
# 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

  1. Identify Pattern: Merging, scheduling, intersection, or resource management?
  2. Choose Sorting Strategy: By start time (merging) or end time (greedy)
  3. Select Template: Use appropriate template from above
  4. Handle Edge Cases: Empty arrays, single intervals, identical intervals
  5. 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

  1. Start with examples: Draw intervals on paper to visualize
  2. Clarify edge cases: What about empty intervals? Point intervals?
  3. Explain sorting choice: Why sorting by start/end time?
  4. Walk through algorithm: Show merge/greedy logic step by step
  5. Optimize incrementally: Start with working solution, then optimize
  6. Practice common patterns: Master the 5 main templates above
  7. Time complexity analysis: Always explain O(n log n) sorting + O(n) processing

Data Structure Conversion Tricks

List to Array (Java)

java
List<int[]> result = new ArrayList<>();
// ... populate result
return result.toArray(new int[result.size()][]);

Efficient Merging in Python

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

LC Examples

2-1) Merge Intervals (LC 56) — Sort + Merge

Sort by start time; merge overlapping intervals by comparing with last merged.

java
// LC 56 - Merge Intervals
// IDEA: Sort by start, merge when current.start <= last.end
// time = O(N log N), space = O(N)
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size()-1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

2-2) Non-overlapping Intervals (LC 435) — Greedy Interval Scheduling

Sort by end time; greedily keep intervals that end earliest to minimize removals.

java
// LC 435 - Non-overlapping Intervals
// IDEA: Greedy — sort by end, count overlapping intervals to remove
// time = O(N log N), space = O(1)
public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int removals = 0, prevEnd = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] < prevEnd) {
            removals++;   // overlap: remove current (keep the one ending earlier)
        } else {
            prevEnd = interval[1];
        }
    }
    return removals;
}

2-3) Insert Interval (LC 57) — Linear Scan + Merge

Insert new interval and merge all overlapping intervals in one pass.

java
// LC 57 - Insert Interval
// IDEA: Three phases — add non-overlapping left, merge overlapping, add right
// time = O(N), space = O(N)
public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;
    // Phase 1: add all intervals that end before newInterval starts
    while (i < n && intervals[i][1] < newInterval[0]) result.add(intervals[i++]);
    // Phase 2: merge overlapping intervals
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    // Phase 3: add remaining intervals
    while (i < n) result.add(intervals[i++]);
    return result.toArray(new int[result.size()][]);
}

2-4) Meeting Rooms II (LC 253) — Min-Heap on End Times

Sort by start; heap tracks earliest ending room — reuse if room ends before next meeting.

java
// LC 253 - Meeting Rooms II
// IDEA: Sort by start; min-heap of end times — reuse room if heap.peek() <= start
// time = O(N log N), space = O(N)
public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int[] iv : intervals) {
        if (!heap.isEmpty() && heap.peek() <= iv[0]) heap.poll();
        heap.offer(iv[1]);
    }
    return heap.size();
}

2-5) Minimum Number of Arrows to Burst Balloons (LC 452) — Greedy

Sort by end; one arrow at interval’s end bursts all overlapping; advance when gap appears.

java
// LC 452 - Minimum Number of Arrows to Burst Balloons
// IDEA: Greedy — sort by end; new arrow only when next start > current end
// time = O(N log N), space = O(1)
public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1, end = points[0][1];
    for (int i = 1; i < points.length; i++)
        if (points[i][0] > end) { arrows++; end = points[i][1]; }
    return arrows;
}

2-6) Interval List Intersections (LC 986) — Two Pointers

Advance the pointer whose interval ends first; record overlap when ranges intersect.

java
// LC 986 - Interval List Intersections
// IDEA: Two pointers — compute intersection, advance pointer with smaller end
// time = O(M+N), space = O(M+N)
public int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> res = new ArrayList<>();
    int i = 0, j = 0;
    while (i < A.length && j < B.length) {
        int lo = Math.max(A[i][0], B[j][0]);
        int hi = Math.min(A[i][1], B[j][1]);
        if (lo <= hi) res.add(new int[]{lo, hi});
        if (A[i][1] < B[j][1]) i++;
        else j++;
    }
    return res.toArray(new int[res.size()][]);
}

2-7) Remove Covered Intervals (LC 1288) — Sort + Greedy

Sort by start asc, end desc; interval is covered if its end ≤ current max end.

java
// LC 1288 - Remove Covered Intervals
// IDEA: Sort start ASC, end DESC; count intervals not covered by running maxEnd
// time = O(N log N), space = O(1)
public int removeCoveredIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    int count = 0, maxEnd = 0;
    for (int[] iv : intervals)
        if (iv[1] > maxEnd) { count++; maxEnd = iv[1]; }
    return count;
}

2-8) Video Stitching (LC 1024) — Greedy Interval Cover

Sort by start; at each frontier pick the clip extending coverage the furthest.

java
// LC 1024 - Video Stitching
// IDEA: Greedy — at current end, pick clip reaching farthest next position
// time = O(N log N), space = O(1)
public int videoStitching(int[][] clips, int time) {
    Arrays.sort(clips, (a, b) -> a[0] - b[0]);
    int count = 0, curEnd = 0, farthest = 0, i = 0;
    while (i < clips.length && curEnd < time) {
        while (i < clips.length && clips[i][0] <= curEnd)
            farthest = Math.max(farthest, clips[i++][1]);
        if (farthest == curEnd) return -1;
        curEnd = farthest;
        count++;
    }
    return curEnd >= time ? count : -1;
}

2-9) Maximum Profit in Job Scheduling (LC 1235) — DP + Binary Search

Sort jobs by end; dp[i] = max profit using first i jobs; binary search for last non-conflicting job.

java
// LC 1235 - Maximum Profit in Job Scheduling
// IDEA: Sort by end; DP + binary search for latest non-overlapping job
// time = O(N log N), space = O(N)
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int n = startTime.length;
    int[][] jobs = new int[n][3];
    for (int i = 0; i < n; i++) jobs[i] = new int[]{endTime[i], startTime[i], profit[i]};
    Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
    int[] dp = new int[n + 1];
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = i;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (jobs[mid-1][0] <= jobs[i][1]) lo = mid;
            else hi = mid - 1;
        }
        dp[i+1] = Math.max(dp[i], dp[lo] + jobs[i][2]);
    }
    return dp[n];
}

2-10) My Calendar I (LC 729) — TreeMap Overlap Check

TreeMap floor/ceiling gives O(log N) overlap detection per booking.

java
// LC 729 - My Calendar I
// IDEA: TreeMap — O(log N) overlap check with floorKey / ceilingKey
// time = O(log N) per booking, space = O(N)
class MyCalendar {
    TreeMap<Integer, Integer> cal = new TreeMap<>();
    public boolean book(int start, int end) {
        Integer prev = cal.floorKey(start), next = cal.ceilingKey(start);
        if ((prev == null || cal.get(prev) <= start) && (next == null || next >= end)) {
            cal.put(start, end);
            return true;
        }
        return false;
    }
}

2-11) Meeting Rooms I (LC 252) — Sort + Adjacent Check

Sort by start time; if any meeting starts before previous ends, overlap exists.

java
// LC 252 - Meeting Rooms
// IDEA: Sort by start; adjacent overlap check
// time = O(N log N), space = O(1)
public boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    for (int i = 1; i < intervals.length; i++)
        if (intervals[i][0] < intervals[i-1][1]) return false;
    return true;
}

2-12) Partition Labels (LC 763) — Build Intervals From Data, Then Merge Priority 5 of 5 — Must know — expect it in almost every loop

Key Idea: the intervals aren’t given — you construct them. Each character c owns the interval [first(c), last(c)]; a valid partition is a merged interval. Because we scan left→right, the intervals arrive already sorted by start, so no sort() is needed: keep a running end = max(end, last[c]) and cut the moment i == end.

Pattern: input → derive intervals → merge is the single most common interval disguise in interviews (also LC 56’s engine, just with implicit input).

Why i == end is the correct cut: end is the max last-occurrence of every character seen so far. When the scan index catches up to it, no character inside [start, i] appears later ⇒ the block is closed and cannot merge with anything to the right.

text
s = a b a b c b a c a d e f e g d e h i j h k l i j
i:  0 1 2 3 4 5 6 7 8 9 ...
last[a]=8, last[b]=5, last[c]=7   -> end grows 0,5,5,5,7,7,8,8,8 -> cut at i=8  (len 9)
                                     next block starts at 9 ...
java
// java
// LC 763 - Partition Labels
// IDEA: last occurrence of each char = that char's interval end; extend & cut in one pass (no sort)
// time = O(N), space = O(1)  (26 letters)
public List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;

    List<Integer> res = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);   // extend current interval
        if (i == end) {                                 // interval closed -> cut here
            res.add(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}
python
# python
# LC 763 - Partition Labels
# IDEA: last[c] = that char's interval end; extend running end, cut when i == end
# time = O(N), space = O(1)  (26 letters)
def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}   # dict comprehension keeps the LAST index
    res, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])              # extend current interval
        if i == end:                         # interval closed -> cut here
            res.append(end - start + 1)
            start = i + 1
    return res

Contrast with LC 56 (2-1): LC 56 must sort because intervals arrive in any order; here the scan order is start order, dropping the cost to O(N).

2-13) Jump Game II (LC 45) — Greedy Cover Over Implicit Intervals

Variation of 2-8 (Video Stitching): the twist is that no interval array is given — index i implicitly covers [i, i + nums[i]], and those intervals are already sorted by start, so the O(N log N) sort disappears and the greedy cover runs in O(N).

Pattern: same two-frontier greedy as LC 1024 — curEnd = boundary of the coverage bought by the jumps so far, farthest = best reach among all intervals starting inside it. Hitting i == curEnd means the current layer is exhausted ⇒ spend one more jump.

java
// java
// LC 45 - Jump Game II
// IDEA: index i = interval [i, i+nums[i]]; greedy cover, +1 jump when current coverage is exhausted
// time = O(N), space = O(1)
public int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {   // stop at n-1: no jump needed once we can reach it
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {                        // exhausted current layer -> must jump
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}
python
# python
# LC 45 - Jump Game II
# IDEA: index i = interval [i, i+nums[i]]; greedy cover, +1 jump when current coverage is exhausted
# time = O(N), space = O(1)
def jump(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):      # stop before last index
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                # exhausted current layer -> must jump
            jumps += 1
            cur_end = farthest
    return jumps

Variation — LC 55 Jump Game: reachability only, drop the jump counter

Same scan; instead of counting layers, fail the moment the scan index passes the farthest covered position (a gap in the cover).

java
// java
// LC 55 - Jump Game
// IDEA: same coverage scan; unreachable once i > farthest (gap in the cover)
// time = O(N), space = O(1)
public boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;               // gap: cover breaks here
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}
python
# python
# LC 55 - Jump Game
# IDEA: same coverage scan; unreachable once i > farthest (gap in the cover)
# time = O(N), space = O(1)
def canJump(nums):
    farthest = 0
    for i, n in enumerate(nums):
        if i > farthest:
            return False                              # gap: cover breaks here
        farthest = max(farthest, i + n)
    return True
Problem Given intervals? Sort needed? Question asked
LC 1024 Video Stitching explicit clips[i] = [s, e] YES — O(N log N) min clips to cover [0, time]
LC 45 Jump Game II implicit [i, i+nums[i]] NO — already start-sorted min intervals to reach n-1
LC 55 Jump Game implicit [i, i+nums[i]] NO is [0, n-1] coverable at all

2-14) Maximum Area of a Piece of Cake (LC 1465) — Gap Scan (Interval Complement)

Key Idea: the complement of a set of cut points is a set of intervals. After sorting the boundaries, the pieces are simply the consecutive differences — plus the two border gaps (0 → first cut and last cut → border), which is where nearly every wrong answer comes from.

Pattern: the same “gaps between sorted boundaries” scan powers free-slot problems (e.g. LC 759 Employee Free Time gaps after merging, LC 228 Summary Ranges). Here the two axes are independent, so maxArea = maxGap(h) * maxGap(w).

java
// java
// LC 1465 - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
// IDEA: complement of sorted cuts = piece intervals; max gap per axis, multiply (axes independent)
// time = O(H log H + V log V), space = O(1)
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
    Arrays.sort(horizontalCuts);
    Arrays.sort(verticalCuts);
    long maxH = maxGap(horizontalCuts, h);
    long maxV = maxGap(verticalCuts, w);
    return (int) ((maxH * maxV) % 1_000_000_007L);   // multiply as long: 1e9 * 1e9 overflows int
}

private long maxGap(int[] cuts, int border) {
    long best = cuts[0];                                    // border gap: 0 -> first cut
    for (int i = 1; i < cuts.length; i++)
        best = Math.max(best, cuts[i] - cuts[i-1]);         // inner gaps: cut -> cut
    return Math.max(best, border - cuts[cuts.length - 1]);  // border gap: last cut -> border
}
python
# python
# LC 1465 - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
# IDEA: complement of sorted cuts = piece intervals; max gap per axis, multiply (axes independent)
# time = O(H log H + V log V), space = O(1)
def maxArea(h, w, horizontalCuts, verticalCuts):
    def max_gap(cuts, border):
        cuts = sorted(cuts)
        best = max(cuts[0], border - cuts[-1])              # the two border gaps
        for a, b in zip(cuts, cuts[1:]):
            best = max(best, b - a)                         # inner gaps
        return best

    return (max_gap(horizontalCuts, h) * max_gap(verticalCuts, w)) % (10 ** 9 + 7)

🚫 Traps: (1) forgetting the two border gaps; (2) taking % on each factor before multiplying in Java int — use long for the product; (3) assuming cuts arrive sorted (they do not).

2-15) Find All Numbers Disappeared in an Array II (LC 4031) — Gap Scan With a Sentinel Priority 4 of 5 — High value — a gap here costs you rounds

Key Idea: same interval complement scan as 2-14, but the answer is the gaps themselves: sort the values, and every jump from prev to x larger than 1 exposes the missing block [prev+1, x-1].

Two things make this harder than LC 163 (Missing Ranges), which hands you a sorted, duplicate-free array already inside [lower, upper]. Here nums is unsorted, may hold duplicates, and may hold values outside the range — all three break the scan, and all three are fixed by one sorted(set(...)) over the clamped values before the loop.

The sentinel prev = lower - 1 is what removes the leading special case: the first real value is then compared against lower exactly like every inner value is compared against its predecessor. The trailing gap has no such trick — nothing follows the last value, so it needs an explicit check after the loop. Forgetting it is the standard wrong answer.

text
nums = [3,9,7], lower = 1, upper = 12
clamp + dedupe + sort -> [3, 7, 9]

prev=0   x=3 -> 3 > 0+1 -> emit [1, 2]    prev=3
         x=7 -> 7 > 3+1 -> emit [4, 6]    prev=7
         x=9 -> 9 > 7+1 -> emit [8, 8]    prev=9   (single missing number = width-1 range)
after loop: prev=9 < 12  -> emit [10, 12]         (trailing gap: NOT covered by the loop)

res = [[1,2], [4,6], [8,8], [10,12]]
python
# python
# LC 4031 - Find All Numbers Disappeared in an Array II
# IDEA: clamp to [lower, upper] + dedupe + sort, then emit each gap between consecutive values
# time = O(N log N), space = O(N)
def findDisappearedNumbers(nums, lower, upper):
    nums = sorted({x for x in nums if lower <= x <= upper})

    res = []
    prev = lower - 1                    # sentinel: makes the leading gap an ordinary gap
    for x in nums:
        if x > prev + 1:                # a hole between prev and x
            res.append([prev + 1, x - 1])
        prev = x

    if prev < upper:                    # trailing gap: the loop can never emit it
        res.append([prev + 1, upper])
    return res
java
// java
// LC 4031 - Find All Numbers Disappeared in an Array II
// IDEA: TreeSet clamps + dedupes + sorts in one pass; then the same gap scan
// time = O(N log N), space = O(N)
public List<List<Integer>> findDisappearedNumbers(int[] nums, int lower, int upper) {
    TreeSet<Integer> seen = new TreeSet<>();
    for (int x : nums)
        if (x >= lower && x <= upper) seen.add(x);

    List<List<Integer>> res = new ArrayList<>();
    int prev = lower - 1;                                      // sentinel
    for (int x : seen) {
        if (x > prev + 1) res.add(Arrays.asList(prev + 1, x - 1));
        prev = x;
    }
    if (prev < upper) res.add(Arrays.asList(prev + 1, upper));  // trailing gap
    return res;
}

🚫 Traps: (1) dropping the trailing gap, or the leading one if you start from nums[0] instead of the sentinel; (2) not filtering values outside [lower, upper] — one stray x < lower makes prev run backwards and emits garbage; (3) not deduping — a repeated value gives x == prev, so x > prev + 1 is false and nothing breaks here, but the same array in the LC 163 two-pointer form emits an inverted range [prev+1, x-1]; (4) [8,8] is a legal answer — a single missing number is a range whose ends coincide, not a value to be skipped.

Problem Input guarantees Extra work before the scan
LC 163 Missing Ranges sorted, unique, all inside [lower, upper] none — scan directly, O(N)
LC 228 Summary Ranges sorted, unique none — emits the present runs, the complement of this
LC 4031 Disappeared Numbers II none of the above clamp + dedupe + sort, O(N log N)
← Back to Cheat Sheets Edit on GitHub →