Greedy Algorithms

def greedy_solution(items):
    # Step 1: Sort or prepare data structure
    items.sort(key=lambda x: x[criterion])
    
    # Step 2: Initialize greedy choice tracking
    result = initial_value
    current_state = initial_state
    
    # Step 3: Make greedy choices
    for item in items:
        if can_select(item, current_state):
            result = update_result(result, item)
            current_state = update_state(current_state, item)
    
    return result

def interval_scheduling(intervals):
    """Select maximum non-overlapping intervals"""
    if not intervals:
        return 0
    
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    
    count = 1
    end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    
    return count

# python
# IDEA: each window of n+1 slots runs the n+1 most frequent remaining tasks (max-heap)
# time = O(T log 26) = O(T), space = O(26)
# Slots a window leaves empty are idle, except in the very last window.
# LC 621 - Task Scheduler
import heapq
import collections

def least_interval(tasks, n):
    freq = collections.Counter(tasks)
    heap = [-count for count in freq.values()]   # max-heap of remaining counts
    heapq.heapify(heap)

    time = 0
    while heap:
        ran = []                                 # counts we ran this cycle
        for _ in range(min(n + 1, len(heap))):   # one cooldown window: run what is available,
            ran.append(heapq.heappop(heap) + 1)  # never visit idle slots (counts are negative)
        for count in ran:
            if count < 0:                        # still has copies left
                heapq.heappush(heap, count)
        # a full window costs n+1; the last window costs only what actually ran
        time += (n + 1) if heap else len(ran)
    return time

// java
// IDEA: each window of n+1 slots runs the n+1 most frequent remaining tasks (max-heap)
// time = O(T log 26) = O(T), space = O(26)
// LC 621 - Task Scheduler
public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) freq[t - 'A']++;
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());  // remaining counts
    for (int f : freq) if (f > 0) heap.offer(f);

    int time = 0;
    while (!heap.isEmpty()) {
        List<Integer> ran = new ArrayList<>();
        int slots = Math.min(n + 1, heap.size());      // run what is available; never visit idle slots
        for (int i = 0; i < slots; i++) ran.add(heap.poll() - 1);
        for (int left : ran) if (left > 0) heap.offer(left);
        time += heap.isEmpty() ? ran.size() : n + 1;   // only the last window may end early
    }
    return time;
}

def greedy_accumulation(prices):
    """Accumulate positive differences (stock trading)"""
    profit = 0
    
    for i in range(1, len(prices)):
        # Greedy: take profit whenever possible
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    
    return profit

def jump_game(nums):
    """Check if can reach end"""
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= len(nums) - 1:
            return True
    
    return True

def jump_game_min_jumps(nums):
    """Minimum jumps to reach end"""
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            current_end = farthest
    
    return jumps

def reorganize_string(s):
    """Reorganize string so no adjacent chars are same"""
    from collections import Counter
    import heapq
    
    # Count frequencies
    count = Counter(s)
    
    # Check if possible
    max_count = max(count.values())
    if max_count > (len(s) + 1) // 2:
        return ""
    
    # Max heap of frequencies
    heap = [(-cnt, char) for char, cnt in count.items()]
    heapq.heapify(heap)
    
    result = []
    prev_count, prev_char = 0, ''
    
    while heap:
        count, char = heapq.heappop(heap)
        result.append(char)
        
        # Add previous back to heap
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_char))
        
        # Update previous
        prev_count = count + 1
        prev_char = char
    
    return ''.join(result)

def fractional_knapsack(items, capacity):
    """Greedy knapsack allowing fractions"""
    # items = [(value, weight), ...]
    # Sort by value/weight ratio
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    
    total_value = 0
    remaining = capacity
    
    for value, weight in items:
        if weight <= remaining:
            total_value += value
            remaining -= weight
        else:
            # Take fraction
            total_value += value * (remaining / weight)
            break
    
    return total_value

Greedy Algorithm Selection Flowchart:

1. Can the problem be solved greedily?
   ├── Does local optimal lead to global optimal? → YES → Use Greedy
   ├── Can you prove greedy correctness? → YES → Use Greedy
   └── NO to both → Use DP or other approach

2. What type of greedy pattern?
   ├── Selection from sorted items → Interval/Activity Selection
   ├── Maximize/minimize at each step → Accumulation Pattern
   ├── Dynamic selection → Priority Queue/Heap
   ├── Position/reach tracking → Jump Game Pattern
   └── Pairing/matching → Two Pointers

3. How to make greedy choice?
   ├── Sort by what criterion?
   │   ├── End time → Interval scheduling
   │   ├── Start time → Merge intervals
   │   ├── Value/weight ratio → Knapsack
   │   └── Custom criterion → Problem specific
   └── No sorting needed → Direct iteration

4. Common greedy strategies:
   ├── Always take the best available
   ├── Never make a choice that blocks future options
   ├── Minimize waste/maximize efficiency
   └── Balance resources evenly

1. Assume optimal solution OPT differs from greedy solution G at some step.
2. Show you can swap OPT's choice at that step with G's choice without making things worse.
3. Repeat until OPT == G → greedy is optimal.

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # sort by weight
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        a, b = find(a), find(b)
        if a == b: return False
        parent[a] = b
        return True

    mst_cost = 0
    for u, v, w in edges:
        if union(u, v):
            mst_cost += w
    return mst_cost

import heapq
from collections import defaultdict

def prim(n, edges):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((w, v))
        graph[v].append((w, u))

    visited = set()
    heap = [(0, 0)]  # (cost, node)
    total = 0
    while heap and len(visited) < n:
        cost, node = heapq.heappop(heap)
        if node in visited: continue
        visited.add(node)
        total += cost
        for w, nei in graph[node]:
            if nei not in visited:
                heapq.heappush(heap, (w, nei))
    return total

# LC 1235 Maximum Profit in Job Scheduling
import bisect

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    dp = [(0, 0)]  # (end_time, max_profit)
    for s, e, p in jobs:
        # Find last job that ends <= s
        i = bisect.bisect_right(dp, (s, float('inf'))) - 1
        new_profit = dp[i][1] + p
        if new_profit > dp[-1][1]:
            dp.append((e, new_profit))
    return dp[-1][1]

# Interval problems
intervals.sort(key=lambda x: x[1])  # By end time
intervals.sort(key=lambda x: x[0])  # By start time

# Value optimization
items.sort(key=lambda x: x.value/x.weight, reverse=True)  # By ratio

# Custom priority
tasks.sort(key=lambda x: (x.deadline, -x.profit))  # Multi-criteria

# Prove: Swapping any two elements won't improve result
def exchange_argument_proof(arr):
    # If swapping arr[i] and arr[j] doesn't improve,
    # then current order is optimal
    pass

# Prove: Greedy solution is at least as good at each step
def stays_ahead_proof(greedy, other):
    # Show: greedy[i] >= other[i] for all i
    pass

# System has matroid structure if:
# 1. Hereditary: Subset of feasible is feasible
# 2. Exchange: Can always extend smaller feasible set

# Prove interval scheduling is optimal
# If we swap any interval in greedy solution with another,
# we either get same or fewer intervals

# Prove jump game solution is minimal
# At each position, greedy reaches at least as far