掃描線（Line Sweep）演算法

# Python - Count maximum overlapping intervals
def maxOverlap(intervals):
    events = []
    
    # Create events for each interval
    for start, end in intervals:
        events.append((start, 1))   # Start event
        events.append((end, -1))     # End event
    
    # Sort events (by time, then by type)
    events.sort(key=lambda x: (x[0], -x[1]))  # Process start before end at same time
    
    # Sweep through events
    max_overlap = 0
    current_overlap = 0
    
    for time, delta in events:
        current_overlap += delta
        max_overlap = max(max_overlap, current_overlap)
    
    return max_overlap

# With position tracking
def maxOverlapPosition(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    
    events.sort(key=lambda x: (x[0], -x[1]))
    
    max_overlap = 0
    max_position = 0
    current_overlap = 0
    
    for time, delta in events:
        current_overlap += delta
        if current_overlap > max_overlap:
            max_overlap = current_overlap
            max_position = time
    
    return max_overlap, max_position

// Java - Maximum interval overlap
public int maxOverlap(int[][] intervals) {
    List<int[]> events = new ArrayList<>();
    
    // Create events
    for (int[] interval : intervals) {
        events.add(new int[]{interval[0], 1});   // Start
        events.add(new int[]{interval[1], -1});  // End
    }
    
    // Sort events
    Collections.sort(events, (a, b) -> {
        if (a[0] != b[0]) return a[0] - b[0];
        return b[1] - a[1];  // Start before end
    });
    
    // Sweep
    int maxOverlap = 0;
    int currentOverlap = 0;
    
    for (int[] event : events) {
        currentOverlap += event[1];
        maxOverlap = Math.max(maxOverlap, currentOverlap);
    }
    
    return maxOverlap;
}

# Python - Sum of overlapping values (e.g., brightness)
def maxWeightedOverlap(weighted_intervals):
    events = []
    
    # weighted_intervals: [(start, end, weight)]
    for start, end, weight in weighted_intervals:
        events.append((start, weight))   # Add weight
        events.append((end, -weight))    # Remove weight
    
    events.sort()
    
    max_weight = 0
    current_weight = 0
    result_position = 0
    
    for position, delta in events:
        current_weight += delta
        if current_weight > max_weight:
            max_weight = current_weight
            result_position = position
    
    return max_weight, result_position

# Track all positions with their weights
def allWeightedPositions(weighted_intervals):
    from collections import defaultdict
    events = defaultdict(int)
    
    for start, end, weight in weighted_intervals:
        events[start] += weight
        events[end] -= weight
    
    sorted_positions = sorted(events.keys())
    positions_weights = {}
    current_weight = 0
    
    for pos in sorted_positions:
        current_weight += events[pos]
        positions_weights[pos] = current_weight
    
    return positions_weights

// Java - Weighted intervals
public int maxWeightedOverlap(int[][] weightedIntervals) {
    // weightedIntervals: [start, end, weight]
    TreeMap<Integer, Integer> events = new TreeMap<>();
    
    for (int[] interval : weightedIntervals) {
        events.put(interval[0], 
                  events.getOrDefault(interval[0], 0) + interval[2]);
        events.put(interval[1], 
                  events.getOrDefault(interval[1], 0) - interval[2]);
    }
    
    int maxWeight = 0;
    int currentWeight = 0;
    
    for (int delta : events.values()) {
        currentWeight += delta;
        maxWeight = Math.max(maxWeight, currentWeight);
    }
    
    return maxWeight;
}

# Python - Building skyline
def getSkyline(buildings):
    events = []
    
    # buildings: [[left, right, height]]
    for left, right, height in buildings:
        events.append((left, -height))  # Start (negative for max heap)
        events.append((right, height))  # End
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    result = []
    heights = [0]  # Ground level
    
    import heapq
    for x, h in events:
        if h < 0:  # Building start
            heapq.heappush(heights, h)
        else:  # Building end
            heights.remove(-h)
            heapq.heapify(heights)
        
        # Check if max height changed
        max_h = -heights[0]
        if not result or result[-1][1] != max_h:
            result.append([x, max_h])
    
    return result

// Java - Skyline
public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]});  // Start
        events.add(new int[]{b[1], b[2]});   // End
    }
    
    Collections.sort(events, (a, b) -> {
        if (a[0] != b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    
    List<List<Integer>> result = new ArrayList<>();
    TreeMap<Integer, Integer> heights = new TreeMap<>();
    heights.put(0, 1);  // Ground
    
    for (int[] event : events) {
        int x = event[0], h = event[1];
        
        if (h < 0) {  // Start
            heights.put(-h, heights.getOrDefault(-h, 0) + 1);
        } else {  // End
            if (heights.get(h) == 1) {
                heights.remove(h);
            } else {
                heights.put(h, heights.get(h) - 1);
            }
        }
        
        int maxH = heights.lastKey();
        if (result.isEmpty() || 
            result.get(result.size() - 1).get(1) != maxH) {
            result.add(Arrays.asList(x, maxH));
        }
    }
    
    return result;
}

# Python - Calendar with multiple bookings
class MyCalendarTwo:
    def __init__(self):
        self.events = []  # List of (time, delta)
    
    def book(self, start, end):
        # Temporarily add new booking
        self.events.append((start, 1))
        self.events.append((end, -1))
        self.events.sort()
        
        # Check if triple booking
        booked = 0
        for time, delta in self.events:
            booked += delta
            if booked >= 3:
                # Remove the temporary booking
                self.events.remove((start, 1))
                self.events.remove((end, -1))
                return False
        
        return True

// Java - Calendar booking
class MyCalendarTwo {
    List<int[]> events;
    
    public MyCalendarTwo() {
        events = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
        events.add(new int[]{start, 1});
        events.add(new int[]{end, -1});
        
        Collections.sort(events, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        
        int booked = 0;
        for (int[] event : events) {
            booked += event[1];
            if (booked >= 3) {
                events.remove(new int[]{start, 1});
                events.remove(new int[]{end, -1});
                return false;
            }
        }
        
        return true;
    }
}

# Python - Range addition using sweep line
def rangeAddition(length, updates):
    # updates: [[start, end, inc]]
    diff = [0] * (length + 1)
    
    for start, end, inc in updates:
        diff[start] += inc
        diff[end + 1] -= inc
    
    # Sweep to get final values
    result = [0] * length
    current = 0
    for i in range(length):
        current += diff[i]
        result[i] = current
    
    return result

# 2D range addition
def rangeAddition2D(m, n, updates):
    diff = [[0] * (n + 1) for _ in range(m + 1)]
    
    for r1, c1, r2, c2, inc in updates:
        diff[r1][c1] += inc
        diff[r1][c2 + 1] -= inc
        diff[r2 + 1][c1] -= inc
        diff[r2 + 1][c2 + 1] += inc
    
    # 2D prefix sum
    result = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            result[i][j] = diff[i][j]
            if i > 0:
                result[i][j] += result[i-1][j]
            if j > 0:
                result[i][j] += result[i][j-1]
            if i > 0 and j > 0:
                result[i][j] -= result[i-1][j-1]
    
    return result

# Python - Merge overlapping intervals using sweep
def mergeIntervals(intervals):
    if not intervals:
        return []
    
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    
    events.sort(key=lambda x: (x[0], -x[1]))
    
    merged = []
    active = 0
    start = 0
    
    for time, delta in events:
        if active == 0 and delta == 1:
            start = time  # New interval starts
        
        active += delta
        
        if active == 0:  # Interval ends
            merged.append([start, time])
    
    return merged

# Python - Longest subarray with sum > 0 after +1/-1 transform
def longestWPI(hours):
    prefix = 0
    max_len = 0
    seen = {}  # { prefix_sum: first_index }

    for i, h in enumerate(hours):
        prefix += 1 if h > 8 else -1

        if prefix > 0:
            # entire [0..i] is valid
            max_len = i + 1
        else:
            # look for earliest j where prefix[j] == prefix[i] - 1
            # subarray [j+1..i] then has sum == 1 > 0
            if (prefix - 1) in seen:
                max_len = max(max_len, i - seen[prefix - 1])

        seen.setdefault(prefix, i)  # only store first occurrence

    return max_len

// Java - LC 1124 Longest Well-Performing Interval
// IDEA: prefix sum +1/-1 transform + HashMap (first occurrence of each sum)
// Key insight: if prefix[i] <= 0, find earliest j where prefix[j] = prefix[i]-1
//              then subarray [j+1..i] has sum = 1 > 0 (well-performing)
// time = O(N), space = O(N)
public int longestWPI(int[] hours) {
    Map<Integer, Integer> map = new HashMap<>();
    int prefix = 0, maxLen = 0;

    for (int i = 0; i < hours.length; i++) {
        prefix += hours[i] > 8 ? 1 : -1;

        if (prefix > 0) {
            maxLen = i + 1;                          // whole prefix is valid
        } else {
            if (map.containsKey(prefix - 1))
                maxLen = Math.max(maxLen, i - map.get(prefix - 1));
        }

        map.putIfAbsent(prefix, i);                  // first occurrence only
    }
    return maxLen;
}

# Python - sweep time forward, one slot per tick, serve earliest deadline
# time = O(n log n), space = O(n)
import heapq

def maxItemsServed(items):
    # items: [(start, end)]  -> item valid on ANY single day in [start, end]
    items.sort()             # 1) sort by START -> items become available in time order

    pq = []                  # 2) MIN heap of END days (deadlines) of open items
    i, day, served = 0, 0, 0
    n = len(items)

    while i < n or pq:
        if not pq:
            day = items[i][0]                 # nothing open -> JUMP time forward

        while i < n and items[i][0] <= day:   # PUSH: everything opened by `day`
            heapq.heappush(pq, items[i][1])
            i += 1

        while pq and pq[0] < day:             # PURGE: lazy-delete expired deadlines
            heapq.heappop(pq)

        if pq:                                # SERVE: earliest deadline, consume the day
            heapq.heappop(pq)
            served += 1
            day += 1

    return served

// Java - Time sweep + deadline heap (LC 1353 shape)
// IDEA: sort by start; min-PQ of end days; each day serve the earliest deadline
// time = O(N log N), space = O(N)
public int maxItemsServed(int[][] items) {
    Arrays.sort(items, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> pq = new PriorityQueue<>();  // end days
    int i = 0, day = 0, served = 0, n = items.length;

    while (i < n || !pq.isEmpty()) {
        if (pq.isEmpty()) day = items[i][0];                 // jump time
        while (i < n && items[i][0] <= day) pq.add(items[i++][1]);  // push
        while (!pq.isEmpty() && pq.peek() < day) pq.poll();  // purge expired
        if (!pq.isEmpty()) { pq.poll(); served++; day++; }    // serve + consume day
    }
    return served;
}

// java
// LC 1235 - Maximum Profit in Job Scheduling
// IDEA: sweep by start; min-heap of (endTime, totalProfitEndingHere);
//       retire jobs with end <= start into a running `best`; push (end, best + profit)
// 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[]{startTime[i], endTime[i], profit[i]};
    Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));      // sweep order = START

    // min-heap on end time: (end, best total profit of a chain ENDING with that job)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    int best = 0;                                                  // best profit fully behind the line

    for (int[] j : jobs) {
        // RETIRE: every job finished by the time this one starts is now compatible
        while (!pq.isEmpty() && pq.peek()[0] <= j[0]) best = Math.max(best, pq.poll()[1]);
        pq.add(new int[]{j[1], best + j[2]});                      // take j on top of `best`
    }
    while (!pq.isEmpty()) best = Math.max(best, pq.poll()[1]);     // drain the tail
    return best;
}

# python
# LC 1235 - Maximum Profit in Job Scheduling
# IDEA: sweep by start; min heap of (end, total profit ending with that job)
# time = O(N log N), space = O(N)
import heapq

class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        jobs = sorted(zip(startTime, endTime, profit))   # sweep order = START
        pq = []          # min heap of (end_time, best_total_profit_ending_with_that_job)
        best = 0         # best profit among jobs already fully behind the sweep line

        for s, e, p in jobs:
            while pq and pq[0][0] <= s:                  # RETIRE finished jobs
                best = max(best, heapq.heappop(pq)[1])
            heapq.heappush(pq, (e, best + p))            # take this job on top of `best`

        while pq:                                        # drain
            best = max(best, heapq.heappop(pq)[1])
        return best

// java
// LC 452 - Minimum Number of Arrows to Burst Balloons
// IDEA: sort by END; keep the current arrow at the smallest end seen; a balloon
//       starting after it forces a new arrow (classic activity-selection sweep)
// time = O(N log N), space = O(1) extra
public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));  // Integer.compare: avoids overflow
    int arrows = 1, end = points[0][1];
    for (int[] p : points) {
        if (p[0] > end) { arrows++; end = p[1]; }   // strict > : touching ends still burst together
    }
    return arrows;
}

# python
# LC 452 - Minimum Number of Arrows to Burst Balloons
# IDEA: sort by END, greedily extend the current shot; new shot when start > current end
# time = O(N log N), space = O(1) extra
class Solution:
    def findMinArrowShots(self, points):
        points.sort(key=lambda x: x[1])          # sweep order = END
        arrows, end = 0, float('-inf')
        for s, e in points:
            if s > end:                          # current arrow cannot reach -> new arrow
                arrows += 1
                end = e
        return arrows

// java
// LC 1465 - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
// IDEA: 1-D gap sweep per axis: sort cuts, max( first cut, last->limit, consecutive diffs )
//       dimensions are independent -> answer = maxGap(h) * maxGap(w)
// time = O(H log H + V log V), space = O(1) extra
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
    long MOD = 1_000_000_007L;
    return (int) (maxGap(horizontalCuts, h) * maxGap(verticalCuts, w) % MOD);  // multiply in long!
}

private long maxGap(int[] cuts, int limit) {
    Arrays.sort(cuts);
    long g = Math.max(cuts[0], limit - cuts[cuts.length - 1]);   // the two EDGE gaps
    for (int i = 1; i < cuts.length; i++)
        g = Math.max(g, cuts[i] - cuts[i - 1]);                  // interior gaps
    return g;
}

# python
# LC 1465 - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
# IDEA: sort each cut list, take the max gap (edges included), multiply the two axes
# time = O(H log H + V log V), space = O(1) extra
class Solution:
    def maxArea(self, h, w, horizontalCuts, verticalCuts):
        MOD = 10 ** 9 + 7

        def max_gap(cuts, limit):
            cuts = sorted(cuts)
            g = max(cuts[0], limit - cuts[-1])          # edge gaps: 0->first, last->limit
            for a, b in zip(cuts, cuts[1:]):
                g = max(g, b - a)                       # interior gaps
            return g

        return (max_gap(horizontalCuts, h) * max_gap(verticalCuts, w)) % MOD

// java
// LC 220 - Contains Duplicate III
// IDEA: sweep index i; TreeSet holds the last `indexDiff` values (evict as the window slides)
//       nearest candidate >= nums[i]-valueDiff is ceiling(); check it is <= nums[i]+valueDiff
// time = O(N log K), space = O(K)   K = indexDiff
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    TreeSet<Long> active = new TreeSet<>();                    // long: |nums[i]| can reach 2^31
    for (int i = 0; i < nums.length; i++) {
        if (i > indexDiff) active.remove((long) nums[i - indexDiff - 1]);   // EVICT out-of-window
        Long c = active.ceiling((long) nums[i] - valueDiff);               // QUERY nearest above
        if (c != null && c <= (long) nums[i] + valueDiff) return true;
        active.add((long) nums[i]);                                        // INSERT current
    }
    return false;
}

# python
# LC 220 - Contains Duplicate III  (bucket sweep: O(N) alternative to an ordered set)
# IDEA: bucket width = valueDiff+1, so two values in the SAME bucket always qualify;
#       otherwise only the two neighbouring buckets can hold a match
# time = O(N), space = O(K)
class Solution:
    def containsNearbyAlmostDuplicate(self, nums, indexDiff, valueDiff):
        if valueDiff < 0 or indexDiff <= 0:
            return False
        w = valueDiff + 1
        buckets = {}                                # bucket id -> the single value in it

        for i, x in enumerate(nums):
            b = x // w                              # floor division: correct for negatives too
            if b in buckets:                        # same bucket -> diff <= valueDiff, guaranteed
                return True
            if b - 1 in buckets and x - buckets[b - 1] <= valueDiff:
                return True
            if b + 1 in buckets and buckets[b + 1] - x <= valueDiff:
                return True
            buckets[b] = x
            if i >= indexDiff:                      # EVICT the value leaving the window
                del buckets[nums[i - indexDiff] // w]
        return False

# python - the two orderings, side by side
events.sort(key=lambda x: (x[0],  x[1]))   # -1 before +1  -> touching does NOT overlap  (half-open)
events.sort(key=lambda x: (x[0], -x[1]))   # +1 before -1  -> touching DOES overlap      (inclusive)

// java - same two orderings
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);  // end(-1) first : half-open
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);  // start(+1) first: inclusive

Problem Analysis Flowchart:

0. Does each time slot serve only ONE interval (pick a subset, not count)?
   ├── YES → Use Time Sweep + Deadline Heap (Template 8)
   │         ├── Sort by start, min heap of END, serve earliest deadline
   │         └── Jump time when heap empty → drops the O(day-range) factor
   └── NO → Continue to 1

1. Are you counting overlapping intervals?
   ├── YES → Use Basic Sweep Line
   │         ├── Fixed capacity? → Track current count
   │         └── Variable weight? → Track weighted sum
   └── NO → Continue to 2

2. Is it about building heights/skyline?
   ├── YES → Use Skyline Template
   │         ├── 1D skyline → Height events
   │         └── 2D rectangles → Coordinate compression
   └── NO → Continue to 3

3. Managing calendar/bookings?
   ├── YES → Use Calendar Template
   │         ├── Single booking → Simple overlap
   │         ├── Double booking → Count = 2 check
   │         └── K-booking → Count = K check
   └── NO → Continue to 4

4. Finding free time/gaps?
   ├── YES → Use Interval Merge
   │         ├── Merge all intervals
   │         └── Find gaps between merged
   └── NO → Continue to 5

5. Batch range updates?
   ├── YES → Use Difference Array
   │         ├── 1D ranges → Simple difference
   │         └── 2D ranges → 2D difference
   └── NO → Use appropriate combination

# Critical: Handle events at same position correctly
# Start before End at same position
events.sort(key=lambda x: (x[0], -x[1]))
# OR End before Start (depends on problem)
events.sort(key=lambda x: (x[0], x[1]))

# Standard conversion
for start, end in intervals:
    events.append((start, +1))  # Enter
    events.append((end, -1))     # Exit
    
# Inclusive vs Exclusive endpoints
events.append((end, -1))     # Exclusive end
events.append((end+1, -1))   # Inclusive end

max_value = 0
current = 0
max_position = 0

for pos, delta in events:
    current += delta
    if current > max_value:
        max_value = current
        max_position = pos

# Use negative for max heap in Python
import heapq
heights = [0]  # Ground level
heapq.heappush(heights, -height)  # Add
max_height = -heights[0]           # Get max

# Compress large coordinate space
coords = set()
for start, end in intervals:
    coords.add(start)
    coords.add(end)
coord_map = {v: i for i, v in enumerate(sorted(coords))}