Interval Patterns: Complete Reference¶

# Standard interval format
intervals: list[list[int]] = [[1, 3], [2, 6], [8, 10], [15, 18]]
# Each interval: [start, end] where start <= end

# Interval with open/closed boundaries
# [1, 3] = closed interval, includes both endpoints
# (1, 3) = open interval, excludes both endpoints
# Most LeetCode problems use closed intervals

# Sort by start time (most common)
intervals.sort(key=lambda x: x[0])

# Sort by end time (greedy selection problems)
intervals.sort(key=lambda x: x[1])

# Sort by start, then by end (for tie-breaking)
intervals.sort(key=lambda x: (x[0], x[1]))

# Two intervals [a_start, a_end] and [b_start, b_end] overlap if:
#   NOT (a_end < b_start OR b_end < a_start)
# Equivalently:
#   a_start <= b_end AND b_start <= a_end

def overlaps(a: list[int], b: list[int]) -> bool:
    return a[0] <= b[1] and b[0] <= a[1]

# After sorting by start, simplified check:
# Current interval starts before previous ends
def overlaps_sorted(prev: list[int], curr: list[int]) -> bool:
    return curr[0] <= prev[1]

# Merge two overlapping intervals
def merge_two(a: list[int], b: list[int]) -> list[int]:
    return [min(a[0], b[0]), max(a[1], b[1])]

# Pattern: interval_merge
# See: docs/patterns/interval/templates.md Section 1 (Base Template)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        """
        Merge overlapping intervals.

        Key Insight:
        - After sorting by start time, overlapping intervals are adjacent
        - Maintain current interval, extend end if overlap, else add new
        - Overlap check: current[0] <= prev_end (since sorted)

        Why sort by start?
        - All intervals starting before current end must overlap
        - No need to look backward after sorting
        """
        if not intervals:
            return []

        # Sort by start time
        intervals.sort(key=lambda x: x[0])

        merged: list[list[int]] = [intervals[0]]

        for interval in intervals[1:]:
            # If current interval overlaps with last merged
            if interval[0] <= merged[-1][1]:
                # Extend the end
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                # No overlap, add new interval
                merged.append(interval)

        return merged

# Without sorting:
# [[8,10], [1,3], [2,6]] → can't detect [1,3] overlaps [2,6]

# After sorting by start:
# [[1,3], [2,6], [8,10]] → adjacent overlaps are easy to detect

# Pattern: interval_insert
# See: docs/patterns/interval/templates.md Section 2

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        """
        Insert new interval into sorted non-overlapping list.

        Key Insight:
        - Already sorted, process in three phases
        - Phase 1: Add all intervals ending before newInterval starts
        - Phase 2: Merge all overlapping intervals
        - Phase 3: Add all intervals starting after newInterval ends

        Why three phases?
        - Clean separation of logic
        - No need to re-sort after insertion
        """
        result: list[list[int]] = []
        i = 0
        n = len(intervals)

        # Phase 1: Add all intervals that end before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Phase 2: Merge overlapping intervals
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)

        # Phase 3: Add remaining intervals
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

# Empty intervals
intervals = [], newInterval = [5,7]
# Result: [[5,7]]

# New interval before all
intervals = [[3,5]], newInterval = [1,2]
# Result: [[1,2], [3,5]]

# New interval after all
intervals = [[1,2]], newInterval = [5,7]
# Result: [[1,2], [5,7]]

# Complete overlap
intervals = [[1,5]], newInterval = [2,3]
# Result: [[1,5]]

# Pattern: interval_scheduling
# See: docs/patterns/interval/templates.md Section 3 (Greedy Selection)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """
        Minimum intervals to remove for no overlaps.

        Key Insight:
        - Equivalent to: total - max non-overlapping intervals
        - Greedy: always keep interval that ends earliest
        - Sort by END time (not start!) for optimal selection

        Why sort by end?
        - Earlier ending = more room for future intervals
        - Greedy choice property: locally optimal → globally optimal
        """
        if not intervals:
            return 0

        # Sort by end time (critical for greedy!)
        intervals.sort(key=lambda x: x[1])

        # Greedy selection: count non-overlapping
        non_overlapping = 1
        prev_end = intervals[0][1]

        for i in range(1, len(intervals)):
            # If current starts after previous ends (no overlap)
            if intervals[i][0] >= prev_end:
                non_overlapping += 1
                prev_end = intervals[i][1]
            # Else: skip current (implicit removal)

        return len(intervals) - non_overlapping

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    """Count removals directly instead of subtracting."""
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])
    removals = 0
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:
            # Overlap detected, remove current (count it)
            removals += 1
        else:
            # No overlap, update prev_end
            prev_end = intervals[i][1]

    return removals

# Pattern: interval_scheduling (group counting variant)
# See: docs/patterns/interval/templates.md Section 4

class Solution:
    def findMinArrowPoints(self, points: List[List[int]]) -> int:
        """
        Minimum arrows to burst all balloons.

        Key Insight:
        - Equivalent to counting non-overlapping groups
        - Sort by end, greedily extend groups
        - New arrow needed when balloon starts after current arrow position

        Why this works:
        - Arrow at x bursts all balloons where start <= x <= end
        - Greedy: shoot at rightmost safe position (end of first balloon)
        """
        if not points:
            return 0

        # Sort by end position
        points.sort(key=lambda x: x[1])

        arrows = 1
        arrow_pos = points[0][1]  # Shoot at end of first balloon

        for i in range(1, len(points)):
            # If balloon starts after current arrow position
            if points[i][0] > arrow_pos:
                arrows += 1
                arrow_pos = points[i][1]

        return arrows

# LC 435: eraseOverlapIntervals
# Remove minimum intervals for no overlaps
# Answer: n - max_non_overlapping

# LC 452: findMinArrowPoints
# Minimum arrows (= number of overlapping groups)
# Answer: max_non_overlapping (same greedy!)

# Key difference:
# - LC 435: count overlaps (n - groups)
# - LC 452: count groups directly

# Single balloon
points = [[1,2]]
# Result: 1

# All overlapping
points = [[1,10], [2,5], [3,8]]
# Result: 1 (one arrow at x=5)

# No overlapping
points = [[1,2], [3,4], [5,6]]
# Result: 3

# Pattern: interval_intersection
# See: docs/patterns/interval/templates.md Section 5

class Solution:
    def intervalIntersection(
        self, firstList: List[List[int]], secondList: List[List[int]]
    ) -> List[List[int]]:
        """
        Find all intersections of two sorted interval lists.

        Key Insight:
        - Use two pointers (like merge sort)
        - Intersection exists if max(starts) <= min(ends)
        - Advance pointer with smaller end (exhausted earlier)

        Why advance smaller end?
        - Interval with smaller end can't intersect future intervals
        - The other interval might still intersect with next intervals
        """
        result: list[list[int]] = []
        i, j = 0, 0

        while i < len(firstList) and j < len(secondList):
            a_start, a_end = firstList[i]
            b_start, b_end = secondList[j]

            # Check for intersection
            start = max(a_start, b_start)
            end = min(a_end, b_end)

            if start <= end:
                result.append([start, end])

            # Advance pointer with smaller end
            if a_end < b_end:
                i += 1
            else:
                j += 1

        return result

# One empty list
firstList = [[1,3], [5,9]], secondList = []
# Result: []

# No intersection
firstList = [[1,2]], secondList = [[3,4]]
# Result: []

# Complete overlap
firstList = [[1,10]], secondList = [[2,5], [7,8]]
# Result: [[2,5], [7,8]]

# Point intersection
firstList = [[1,3]], secondList = [[3,5]]
# Result: [[3,3]]

# Standard overlap (closed intervals)
# Intervals [a,b] and [c,d] overlap if: a <= d AND c <= b

# After sorting by start:
# Current overlaps with previous if: curr_start <= prev_end

# After sorting by end:
# Current overlaps with previous if: curr_start < prev_end
# Note: < not <= because we're greedy (want equality to mean "touch")

# MERGE PATTERN (sort by start)
intervals.sort(key=lambda x: x[0])
for curr in intervals[1:]:
    if curr[0] <= merged[-1][1]:  # Overlap
        merged[-1][1] = max(merged[-1][1], curr[1])  # Extend
    else:
        merged.append(curr)

# SCHEDULING PATTERN (sort by end)
intervals.sort(key=lambda x: x[1])
for curr in intervals[1:]:
    if curr[0] >= prev_end:  # No overlap
        count += 1
        prev_end = curr[1]

# INTERSECTION PATTERN (two pointers)
while i < len(A) and j < len(B):
    start, end = max(A[i][0], B[j][0]), min(A[i][1], B[j][1])
    if start <= end:
        result.append([start, end])
    if A[i][1] < B[j][1]:
        i += 1
    else:
        j += 1

def merge(intervals: List[List[int]]) -> List[List[int]]:
    """Sort by start, merge adjacent overlaps."""
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for curr in intervals[1:]:
        if curr[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], curr[1])
        else:
            merged.append(curr)

    return merged

def insert(intervals: List[List[int]], new: List[int]) -> List[List[int]]:
    """Three-phase: before, merge, after."""
    result = []
    i = 0
    n = len(intervals)

    # Phase 1: Before overlap
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i])
        i += 1

    # Phase 2: Merge overlapping
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    result.append(new)

    # Phase 3: After overlap
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

def max_non_overlapping(intervals: List[List[int]]) -> int:
    """Sort by end, greedily select non-overlapping."""
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])
    count = 1
    prev_end = intervals[0][1]

    for curr in intervals[1:]:
        if curr[0] >= prev_end:  # No overlap
            count += 1
            prev_end = curr[1]

    return count

# LC 435: return len(intervals) - max_non_overlapping(intervals)
# LC 452: return max_non_overlapping(intervals)  # (with > instead of >=)

def interval_intersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    """Two-pointer merge for intersections."""
    result = []
    i, j = 0, 0

    while i < len(A) and j < len(B):
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])

        if start <= end:
            result.append([start, end])

        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1

    return result

def overlaps(a: List[int], b: List[int]) -> bool:
    """Check if two intervals overlap (closed intervals)."""
    return a[0] <= b[1] and b[0] <= a[1]

def merge_two(a: List[int], b: List[int]) -> List[int]:
    """Merge two overlapping intervals."""
    return [min(a[0], b[0]), max(a[1], b[1])]

def intersection(a: List[int], b: List[int]) -> Optional[List[int]]:
    """Get intersection of two intervals, or None."""
    start = max(a[0], b[0])
    end = min(a[1], b[1])
    return [start, end] if start <= end else None