def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    """Minimum intervals to remove for non-overlap"""
    if not intervals:
        return 0
    
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    
    count = 0
    prev_end = float('-inf')
    
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end  # Keep this interval
        else:
            count += 1  # Remove overlapping
    
    return count

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """Minimum meeting rooms required"""
    import heapq
    
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])
    
    # Min heap of end times
    heap = []
    heapq.heappush(heap, intervals[0][1])
    
    for i in range(1, len(intervals)):
        # If room is free, reuse it
        if intervals[i][0] >= heap[0]:
            heapq.heappop(heap)
        
        heapq.heappush(heap, intervals[i][1])
    
    return len(heap)

def max_events(events: list[list[int]]) -> int:
    """Maximum events you can attend (one per day)"""
    import heapq
    
    events.sort()
    max_day = max(e[1] for e in events)
    
    i = 0
    count = 0
    heap = []  # End days of available events
    
    for day in range(1, max_day + 1):
        # Add events starting today
        while i < len(events) and events[i][0] == day:
            heapq.heappush(heap, events[i][1])
            i += 1
        
        # Remove expired events
        while heap and heap[0] < day:
            heapq.heappop(heap)
        
        # Attend event ending soonest
        if heap:
            heapq.heappop(heap)
            count += 1
    
    return count

def can_jump(nums: list[int]) -> bool:
    """Can reach last index"""
    max_reach = 0
    
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
        if max_reach >= len(nums) - 1:
            return True
    
    return True

def jump(nums: list[int]) -> int:
    """Minimum jumps to reach end"""
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            if current_end >= n - 1:
                break
    
    return jumps

def video_stitching(clips: list[list[int]], time: int) -> int:
    """Minimum clips to cover [0, time]"""
    clips.sort()
    
    count = 0
    current_end = 0
    i = 0
    n = len(clips)
    
    while current_end < time:
        farthest = current_end
        
        # Find clip that extends farthest
        while i < n and clips[i][0] <= current_end:
            farthest = max(farthest, clips[i][1])
            i += 1
        
        if farthest == current_end:
            return -1  # Can't extend
        
        current_end = farthest
        count += 1
    
    return count

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    """Find starting station for circular trip"""
    n = len(gas)
    total_tank = 0
    current_tank = 0
    start = 0
    
    for i in range(n):
        gain = gas[i] - cost[i]
        total_tank += gain
        current_tank += gain
        
        if current_tank < 0:
            # Can't start from any station before i+1
            start = i + 1
            current_tank = 0
    
    return start if total_tank >= 0 else -1

def candy(ratings: list[int]) -> int:
    """Minimum candies so higher rating gets more"""
    n = len(ratings)
    candies = [1] * n
    
    # Left to right pass
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    
    # Right to left pass
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    
    return sum(candies)

def least_interval(tasks: list[str], n: int) -> int:
    """Minimum intervals to complete all tasks with cooldown"""
    from collections import Counter
    
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)
    
    # Formula: (max_freq - 1) * (n + 1) + max_count
    # But at least len(tasks) if no idle needed
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

def reorganize_string(s: str) -> str:
    """Rearrange so no adjacent chars are same"""
    from collections import Counter
    import heapq
    
    freq = Counter(s)
    n = len(s)
    
    # Check if possible
    max_freq = max(freq.values())
    if max_freq > (n + 1) // 2:
        return ""
    
    # Max heap of (-count, char)
    heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(heap)
    
    result = []
    prev_count, prev_char = 0, ''
    
    while heap:
        count, char = heapq.heappop(heap)
        result.append(char)
        
        # Add previous char back if it has remaining count
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_char))
        
        prev_count = count + 1  # Used one
        prev_char = char
    
    return ''.join(result)

def partition_labels(s: str) -> list[int]:
    """Partition into max parts where each letter in at most one part"""
    # Find last occurrence of each character
    last = {c: i for i, c in enumerate(s)}
    
    result = []
    start = 0
    end = 0
    
    for i, c in enumerate(s):
        end = max(end, last[c])
        
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    
    return result

def is_possible(nums: list[int]) -> bool:
    """Split into subsequences of length >= 3"""
    from collections import Counter
    
    freq = Counter(nums)
    need = Counter()  # Subsequences waiting for this number
    
    for num in nums:
        if freq[num] == 0:
            continue
        
        if need[num] > 0:
            # Extend existing subsequence
            need[num] -= 1
            need[num + 1] += 1
        elif freq[num + 1] > 0 and freq[num + 2] > 0:
            # Start new subsequence
            freq[num + 1] -= 1
            freq[num + 2] -= 1
            need[num + 3] += 1
        else:
            return False
        
        freq[num] -= 1
    
    return True

def max_profit(prices: list[int]) -> int:
    """Max profit with multiple transactions"""
    profit = 0
    
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    
    return profit

def max_profit(prices: list[int], fee: int) -> int:
    """Max profit with transaction fee"""
    cash = 0           # Max profit if not holding
    hold = -prices[0]  # Max profit if holding
    
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    
    return cash

def remove_duplicate_letters(s: str) -> str:
    """Remove duplicates for smallest lexicographic result"""
    from collections import Counter
    
    last_occurrence = {c: i for i, c in enumerate(s)}
    stack = []
    seen = set()
    
    for i, c in enumerate(s):
        if c in seen:
            continue
        
        # Remove larger chars if they appear later
        while stack and c < stack[-1] and last_occurrence[stack[-1]] > i:
            seen.remove(stack.pop())
        
        stack.append(c)
        seen.add(c)
    
    return ''.join(stack)

def remove_kdigits(num: str, k: int) -> str:
    """Remove k digits for smallest number"""
    stack = []
    
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # Remove remaining k digits from end
    stack = stack[:-k] if k else stack
    
    # Remove leading zeros and handle empty
    return ''.join(stack).lstrip('0') or '0'

def num_rescue_boats(people: list[int], limit: int) -> int:
    """Minimum boats (max 2 people, max weight limit)"""
    people.sort()
    boats = 0
    left, right = 0, len(people) - 1
    
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        boats += 1
    
    return boats

def find_content_children(greed: list[int], cookies: list[int]) -> int:
    """Maximize content children"""
    greed.sort()
    cookies.sort()
    
    child = 0
    cookie = 0
    
    while child < len(greed) and cookie < len(cookies):
        if cookies[cookie] >= greed[child]:
            child += 1
        cookie += 1
    
    return child

def two_city_sched_cost(costs: list[list[int]]) -> int:
    """Send n people to each city with minimum cost"""
    # Sort by cost difference (city A - city B)
    costs.sort(key=lambda x: x[0] - x[1])
    
    total = 0
    n = len(costs) // 2
    
    # First half goes to city A, second half to city B
    for i in range(n):
        total += costs[i][0] + costs[i + n][1]
    
    return total

def find_min_arrow_shots(points: list[list[int]]) -> int:
    """Minimum arrows to burst all balloons"""
    if not points:
        return 0
    
    # Sort by end coordinate
    points.sort(key=lambda x: x[1])
    
    arrows = 1
    arrow_pos = points[0][1]
    
    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end
    
    return arrows

def reconstruct_queue(people: list[list[int]]) -> list[list[int]]:
    """Reconstruct queue by (height, count_taller_ahead)"""
    # Sort by height descending, then by k ascending
    people.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    for person in people:
        result.insert(person[1], person)
    
    return result

def find_maximized_capital(k: int, w: int, profits: list[int], capital: list[int]) -> int:
    """Select at most k projects to maximize capital"""
    import heapq
    
    n = len(profits)
    projects = sorted(zip(capital, profits))
    
    max_heap = []  # Max heap of profits for affordable projects
    i = 0
    
    for _ in range(k):
        # Add all affordable projects
        while i < n and projects[i][0] <= w:
            heapq.heappush(max_heap, -projects[i][1])
            i += 1
        
        if not max_heap:
            break
        
        w += -heapq.heappop(max_heap)
    
    return w

def min_cost_to_hire_workers(quality: list[int], wage: list[int], k: int) -> float:
    """Minimum cost to hire k workers fairly"""
    import heapq
    
    n = len(quality)
    
    # Sort by wage/quality ratio
    workers = sorted([(w / q, q) for w, q in zip(wage, quality)])
    
    result = float('inf')
    quality_sum = 0
    max_heap = []  # Max heap of qualities
    
    for ratio, q in workers:
        heapq.heappush(max_heap, -q)
        quality_sum += q
        
        if len(max_heap) > k:
            quality_sum += heapq.heappop(max_heap)  # Remove max quality
        
        if len(max_heap) == k:
            result = min(result, ratio * quality_sum)
    
    return result