區間（Intervals）

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

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()][]);
}

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;
}

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

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();
}

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

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?

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

def has_overlap(interval1, interval2):
    """Check if two intervals overlap (any order)"""
    start1, end1 = interval1
    start2, end2 = interval2
    return start1 < end2 and start2 < end1

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

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

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

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]

# 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])

# 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

# 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()

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

# 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

// 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()][]);
}

// 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;
}

// 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()][]);
}

// 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();
}

// 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;
}

// 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()][]);
}

// 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;
}

// 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;
}

// 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];
}

// 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;
    }
}

// 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;
}

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

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

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

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

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
# 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
// 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;
}