Greedy Pattern

def max_non_overlapping_intervals(intervals):
    """Maximum number of non-overlapping intervals"""
    if not intervals:
        return 0
    
    # GREEDY CHOICE: sort by end time -- earliest ending first
    intervals.sort(key=lambda x: x[1])
    
    count = 1                   # Always take the first interval
    end = intervals[0][1]       # Track where the last selected interval ends
    
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:   # No overlap with the last selected interval
            count += 1
            end = intervals[i][1]    # Update the end boundary
    
    return count

def min_meeting_rooms(intervals):
    """Minimum rooms needed for all meetings"""
    if not intervals:
        return 0
    
    # Separate and sort start times and end times independently
    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])
    
    rooms = 0          # Currently occupied rooms
    max_rooms = 0      # Peak occupancy = answer
    s, e = 0, 0        # Pointers into starts and ends arrays
    
    while s < len(starts):
        if starts[s] < ends[e]:  # A meeting starts before the next one ends
            rooms += 1           # Need one more room
            s += 1
        else:                    # A meeting ends before (or when) the next starts
            rooms -= 1           # Free up a room
            e += 1
        max_rooms = max(max_rooms, rooms)
    
    return max_rooms

def can_jump(nums):
    """Can we reach the last index?"""
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:        # We cannot reach this index -- stuck!
            return False
        max_reach = max(max_reach, i + nums[i])  # Extend our reach
    
    return True

def min_jumps(nums):
    """Minimum jumps to reach last index (BFS-level greedy)"""
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0     # Rightmost index reachable with 'jumps' jumps
    farthest = 0        # Farthest index reachable from any index in current level
    
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:       # We have explored the entire current level
            jumps += 1             # Take one more jump
            current_end = farthest # New level boundary
    
    return jumps

def can_complete_circuit(gas, cost):
    """Find starting gas station to complete circuit"""
    total_tank = 0       # Tracks global feasibility (sum of all net gains)
    current_tank = 0     # Tracks local feasibility from current start
    start = 0            # Candidate starting station
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        if current_tank < 0:       # Ran out of gas starting from 'start'
            start = i + 1           # Skip all stations from old start to i
            current_tank = 0        # Reset for fresh start
    
    return start if total_tank >= 0 else -1  # Global check: is a solution possible?

def partition_labels(s):
    """Partition string so each letter appears in at most one part"""
    # PASS 1: Find last occurrence of each character
    last = {c: i for i, c in enumerate(s)}
    
    result = []
    start = 0    # Left boundary of current partition
    end = 0      # Right boundary (expands as we see characters with later last-occurrences)
    
    # PASS 2: Expand partition greedily, cut when all intervals are closed
    for i, c in enumerate(s):
        end = max(end, last[c])   # Expand to include c's full range
        
        if i == end:              # All characters in [start, end] have their last occurrence here
            result.append(end - start + 1)
            start = i + 1         # Begin next partition
    
    return result