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

import heapq

def activity_selection_heap(tasks):
    """Select activities using priority queue"""
    # Count frequency or priority
    freq = collections.Counter(tasks)
    
    # Max heap (negate for min heap)
    heap = [(-count, task) for task, count in freq.items()]
    heapq.heapify(heap)
    
    result = []
    while heap:
        count1, task1 = heapq.heappop(heap)
        result.append(task1)
        
        if heap:
            count2, task2 = heapq.heappop(heap)
            result.append(task2)
            
            # Add back if still available
            if count1 < -1:
                heapq.heappush(heap, (count1 + 1, task1))
            if count2 < -1:
                heapq.heappush(heap, (count2 + 1, task2))
    
    return result

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

// LC 55 - Jump Game
// IDEA: Greedy — track max reachable index; fail if current index exceeds it
// time = O(N), space = O(1)
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

# 055 Jump Game
# V0
class Solution(object):
    def canJump(self, nums):
        # edge case
        if not nums:
            return True
        cur = 0
        for i in range(len(nums)):
            if cur < i:
                return False
            cur = max(cur, i + nums[i])
        return True

// LC 45 - Jump Game II
// IDEA: Greedy — track current window end and farthest; jump when window end reached
// 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++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = farthest; }
    }
    return jumps;
}

# 045 Jump Game II
# V0
# IDEA : GREEDY
"""
Steps:
    step 1) Initialize three integer variables: jumps to count the number of jumps, currentJumpEnd to mark the end of the range that we can jump to, and farthest to mark the farthest place that we can reach. Set each variable to zero
    step 2) terate over nums. Note that we exclude the last element from our iteration because as soon as we reach the last element, we do not need to jump anymore.
            - Update farthest to i + nums[i] if the latter is larger.
            - If we reach currentJumpEnd, it means we finished the current jump, and can begin checking the next jump by setting currentJumpEnd = farthest.
    step 3) return jumps
"""
class Solution:
    def jump(self, nums: List[int]) -> int:
            jumps = 0
            current_jump_end = 0
            farthest = 0
            for i in range(len(nums) - 1):
                # we continuously find the how far we can reach in the current jump
                farthest = max(farthest, i + nums[i])
                # if we have come to the end of the current jump,
                # we need to make another jump
                if i == current_jump_end:
                    jumps += 1
                    current_jump_end = farthest
            return jumps

# V1
# IDEA : GREEDY
# https://leetcode.com/problems/jump-game-ii/discuss/1672485/Python-Greedy
class Solution:
    def jump(self, nums: List[int]) -> int:
        l = r = res = farthest = 0
        while r < len(nums) - 1:
            for idx in range(l, r+1):
                farthest = max(farthest, idx + nums[idx])
            l = r+1
            r = farthest 
            res += 1
        return res

// LC 122 - Best Time to Buy and Sell Stock II
// IDEA: Greedy — sum all positive consecutive differences
// time = O(N), space = O(1)
public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++)
        if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1];
    return profit;
}

# 122 Best Time to Buy and Sell Stock II
class Solution:
    def maxProfit(self, prices):
        profit = 0
        for i in range(0,len(prices)-1):
            if prices[i+1] > prices[i]:
                # have to sale last stock, then buy a new one
                # and sum up the price difference into profit
                profit += prices[i+1] - prices[i]
        return profit

// LC 134 - Gas Station
// IDEA: Greedy — reset start when cumulative surplus goes negative; check total >= 0
// time = O(N), space = O(1)
public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, remain = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff; remain += diff;
        if (remain < 0) { start = i + 1; remain = 0; }
    }
    return total >= 0 ? start : -1;
}

# 134 Gas Station
# V0
# IDEA : GREEDY
# IDEA : if sum(gas) - sum(cost) > 0, => THERE MUST BE A SOLUTION
# IDEA : since it's circular (symmetry), we can maintain "total" (e.g. total += gas[i] - cost[i]) of (gas[i], cost[i]) for each index as their "current sum"
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        start = remain = total = 0
        for i in range(len(gas)):
            remain += gas[i] - cost[i]
            total += gas[i] - cost[i]
            if remain < 0:
                remain = 0
                start = i + 1
        return -1 if total < 0 else start

// LC 767 - Reorganize String
// IDEA: Max-heap by frequency; always pick top that differs from last placed char
// time = O(N log K), space = O(K)  K = distinct chars
public String reorganizeString(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
    for (int i = 0; i < 26; i++) if (freq[i] > 0) pq.offer(new int[]{i, freq[i]});
    StringBuilder sb = new StringBuilder();
    int[] prev = null;
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        sb.append((char)('a' + curr[0]));
        if (prev != null) pq.offer(prev);
        curr[1]--;
        prev = curr[1] > 0 ? curr : null;
    }
    return sb.length() == s.length() ? sb.toString() : "";
}

# LC 767. Reorganize String

# V0 
# IDEA : GREEDY + COUNTER
# IDEA : 
#  step 1) order exists count (big -> small)
#  step 2) select the element which is "most remaining" and DIFFERENT from last ans element and append such element to the end of ans
#  step 3) if can't find such element, return ""
class Solution(object):
    def reorganizeString(self, S):
        cnt = collections.Counter(S)
        # Be aware of it : ans = "#" -> not to have error in ans[-1] when first loop
        ans = '#'
        while cnt:
            stop = True
            for v, c in cnt.most_common():
                """
                NOTE !!! trick here

                1) we only compare last element in ans and current key (v), if they are different, then append
                2) we break at the end of each for loop -> MAKE SURE two adjacent characters are not the same.
                3) we use a flag "stop", to decide whether should stop while loop or not
                """
                if v != ans[-1]:
                    stop = False
                    ans += v
                    cnt[v] -= 1
                    if not cnt[v]:
                        del cnt[v]
                    """
                    NOTE !!!
                     -> we BREAK right after each op, since we want to get next NEW most common element from "updated" cnt.most_common()
                    """
                    break
            # Be aware of it : if there is no valid "v", then the while loop will break automatically at this condition (stop = True)
            if stop:
                break
        return ans[1:] if len(ans[1:]) == len(S) else ''

// LC 984 - String Without AAA or BBB
// IDEA: Greedy — write higher-count char unless 2 consecutive, then must switch
// time = O(A+B), space = O(1)
public String strWithout3a3b(int a, int b) {
    StringBuilder res = new StringBuilder();
    int continueA = 0;
    int continueB = 0;

    while (a > 0 || b > 0) {
        boolean writeA = false;

        // Priority 1: Must switch if 2 consecutive
        if (continueB == 2) {
            writeA = true;
        } else if (continueA == 2) {
            writeA = false;
        } else {
            // Priority 2: Greedy - write the one with more remaining
            writeA = a >= b;
        }

        if (writeA) {
            res.append("a");
            a--;
            continueA++;
            continueB = 0; // Reset other counter
        } else {
            res.append("b");
            b--;
            continueB++;
            continueA = 0; // Reset other counter
        }
    }
    return res.toString();
}

// V1: Using last 2 characters check (Editorial)
public String strWithout3a3b_v1(int A, int B) {
    StringBuilder ans = new StringBuilder();
    while (A > 0 || B > 0) {
        boolean writeA = false;
        int L = ans.length();
        // Check last 2 chars
        if (L >= 2 && ans.charAt(L-1) == ans.charAt(L-2)) {
            if (ans.charAt(L-1) == 'b') writeA = true;
        } else {
            if (A >= B) writeA = true;
        }

        if (writeA) { A--; ans.append('a'); }
        else { B--; ans.append('b'); }
    }
    return ans.toString();
}

// V2: PQ approach (similar to Reorganize String)
// Max heap: always pick char with highest remaining count
// If blocked by consecutive constraint, pick second highest

// LC 621 - Task Scheduler
// IDEA: Greedy formula — (maxFreq-1)*(n+1) + #tasks_with_maxFreq; also can't be less than total
// time = O(N), space = O(1)
public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) freq[t - 'A']++;
    int maxFreq = 0;
    for (int f : freq) maxFreq = Math.max(maxFreq, f);
    int countMax = 0;
    for (int f : freq) if (f == maxFreq) countMax++;
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMax);
}

# LC 621. Task Scheduler
# V0
# pattern :
#    =============================================================================
#    -> task_time = (max_mission_count - 1) * (n + 1) + (number_of_max_mission)
#    =============================================================================
#   
#    -> Example 1) :
#    ->  AAAABBBBCCD, n=3
#    => THE EXPECTED tuned missions is like : ABXXABXXABXXAB
#    -> (4 - 1) * (3 + 1) + 2 = 14
#    -> 4 is the "how many missions the max mission has" (AAAA or BBBB)
#    -> 3 is n
#    -> 2 is "how many mission have max mission count" -> A and B. so it's 2
#    -> in sum,
#    -> (4 - 1) * (3 + 1) is for ABXXABXXABXX
#    -> and 2 is for AB
#
#   -> Example 2) :
#   -> AAABBB, n = 2
#   -> THE EXPECTED tuned missions is like : ABXABXAB
#   -> (3 - 1) * (2 + 1) + (2) = 8
class Solution(object):
    def leastInterval(self, tasks, n):
        count = collections.Counter(tasks)
        most = count.most_common()[0][1]
        num_most = len([i for i, v in count.items() if v == most])
        """
        example 1 : tasks = ["A","A","A","B","B","B"], n = 2
            -> we can split tasks as : A -> B -> idle -> A -> B -> idle -> A -> B
               -> 1) so there are 3-1 group. e.g. (A -> B -> idle), (A -> B -> idle)
                     and each group has (n+1) elements. e.g. (A -> B -> idle)
               -> 2) and the remain element is num_most. e.g. (A, B)
               -> 3) so total cnt = (3-1) * (2+1) + 2 = 8
    
        example 2 : tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
            -> we can split tasks as A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A
                -> 1) so there are 6-1 group. e.g. (A -> B -> C), (A -> D -> E), (A -> F -> G), (A -> idle -> idle), (A -> idle -> idle)
                      and each group has (n+1) elements. e.g. (A,B,C) .... (as above)
                -> 2) and the remain element is num_most. e.g. (A) 
                -> 3) so total cnt = (6-1)*(2+1) + 1 =  16
        """
        time = (most - 1) * (n + 1) + num_most
        return max(time, len(tasks)) # when idle slots go negative, just run all tasks sequentially

// LC 1710 - Maximum Units on a Truck
// IDEA: Sort by units descending; greedily load boxes until truck is full
// time = O(N log N), space = O(1)
public int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
    int total = 0;
    for (int[] box : boxTypes) {
        int take = Math.min(box[0], truckSize);
        total += take * box[1];
        truckSize -= take;
        if (truckSize == 0) break;
    }
    return total;
}

# LC 1710. Maximum Units on a Truck
# V0
# IDEA : GREEDY + sorting
class Solution(object):
    def maximumUnits(self, boxTypes, truckSize):
        # boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
        # edge case
        if not boxTypes or not truckSize:
            return 0
        """
        NOTE : we sort on sort(key=lambda x : -x[1])

            -> if unit is bigger, we can get bigger aggregated result (n * unit)
        """
        boxTypes.sort(key=lambda x : -x[1])
        res = 0
        for n, unit in boxTypes:
            # case 1 : truckSize == 0, break for loop and return ans
            if truckSize == 0:
                break
            # case 2 : truckSize < n, we CAN'T add all n to truck, but CAN only add (truckSize * unit) amount to truck
            elif truckSize < n:
                res += (truckSize * unit)
                truckSize = 0
                break
            # case 3 : normal case, it's OK to put all (n * unit) to truck once
            else:      
                res += (n * unit)
                truckSize -= n
        return res

# V1
# IDEA : GREEDY
# https://leetcode.com/problems/maximum-units-on-a-truck/discuss/1045318/Python-solution
class Solution(object):
    def maximumUnits(self, boxTypes, truckSize):
        boxTypes.sort(key = lambda x: -x[1])
        n = len(boxTypes)
        result = 0
        i = 0
        while truckSize >= boxTypes[i][0]:
            result += boxTypes[i][1] * boxTypes[i][0]
            truckSize -= boxTypes[i][0]
            i += 1
            if i == n:
                return result
        result += truckSize * boxTypes[i][1]
        return result

# Check if there is a matching complement prefix sum
if (running_prefix - target) in seen_prefixes:
    cnt += 1

    # GREEDY RESET: Clear everything to prevent overlaps
    seen_prefixes.clear()
    running_prefix = 0

nums = [-1, 3, 5, 1, 4, 2, -9],  target = 6

Legend: prefix = running prefix sum
        complement = prefix - target  (what we look for in `seen`)
        seen = prefix sums since the LAST reset

┌─────┬────────┬────────────┬────────┬─────┬──────────────────┐
│ num │ prefix │ complement │ found? │ cnt │ seen (this seg)  │
├─────┼────────┼────────────┼────────┼─────┼──────────────────┤
│ init│   0    │     -      │   -    │  0  │ {0}              │
│ -1  │  -1    │    -7      │  No    │  0  │ {0,-1}           │
│  3  │   2    │    -4      │  No    │  0  │ {0,-1,2}         │
│  5  │   7    │     1      │  No    │  0  │ {0,-1,2,7}       │
│  1  │   8    │     2      │  YES   │  1  │ RESET → {0}      │  ← subarray [5,1] sums to 6
│  4  │   4    │    -2      │  No    │  1  │ {0,4}            │
│  2  │   6    │     0      │  YES   │  2  │ RESET → {0}      │  ← subarray [4,2] sums to 6
│ -9  │  -9    │   -15      │  No    │  2  │ {0,-9}           │
└─────┴────────┴────────────┴────────┴─────┴──────────────────┘

Answer: cnt = 2   (subarrays [5,1] and [4,2] are non-overlapping)

Why NOT wait for a bigger subarray?

Full array [3,5,1,4,2,-9] also sums to 6, but choosing it would
"swallow" indices that could otherwise host BOTH [5,1] and [4,2]:

  [-1,  3,  5,  1,  4,  2, -9]
            └──6──┘                ← take EARLY  →  1 subarray, rest still free
                     └──6──┘       ← then take another →  total = 2  ✅

  [-1,  3,  5,  1,  4,  2, -9]
        └──────── 6 ────────┘      ← greedy-late swallows everything → total = 1  ❌

// java
// LC 1546 - Max Non-Overlapping Subarrays With Sum = Target
// IDEA: Greedy + prefix sum + hashset; on match, count and RESET history
// time = O(N), space = O(N)
public int maxNonOverlapping(int[] nums, int target) {
    Set<Integer> seen = new HashSet<>();
    seen.add(0);                 // base prefix
    int running = 0, cnt = 0;
    for (int num : nums) {
        running += num;
        if (seen.contains(running - target)) {
            cnt++;
            seen.clear();        // GREEDY RESET: prevent overlap
            running = 0;
        }
        seen.add(running);       // re-adds 0 right after a reset
    }
    return cnt;
}

# python
# LC 1546 - Max Non-Overlapping Subarrays With Sum = Target
# IDEA: Greedy + prefix sum + hashset; on match, count and RESET history
# time = O(N), space = O(N)
class Solution(object):
    def maxNonOverlapping(self, nums, target):
        seen_prefixes = set([0])   # base prefix
        running_prefix = 0
        cnt = 0
        for num in nums:
            running_prefix += num
            if (running_prefix - target) in seen_prefixes:
                cnt += 1
                # GREEDY RESET: clear everything to prevent overlaps
                seen_prefixes.clear()
                running_prefix = 0
            seen_prefixes.add(running_prefix)  # re-adds 0 right after a reset
        return cnt

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