Minimal, copy-paste Java for interval scheduling, activity selection, and greedy on arrays/strings with sorting.

Contents

Greedy Algorithm Overview

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work well when:

  • The problem has optimal substructure
  • The greedy choice property holds (locally optimal choice leads to global optimum)
  • No need to reconsider previous choices

Key Principles

  1. Greedy Choice Property: A global optimum can be reached by making locally optimal choices
  2. Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  3. No Backtracking: Once a choice is made, it’s never reconsidered

Interval Scheduling

Greedy approach: Sort by end time, always pick the interval that ends earliest.

// Non-overlapping Intervals
static int eraseOverlapIntervals(int[][]& intervals) {
    if(intervals.length == 0) return 0;

    sort(intervals /* elements of intervals */, [](int[] a, int[] b) {
        return a[1] < b[1];  // Sort by end time
    });

    int count = 1;
    int end = intervals[0][1];

    for(int i = 1; i < intervals.length; i++) {
        if(intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }

    return intervals.length - count;
}

Activity Selection

Similar to interval scheduling, select maximum number of non-overlapping activities.

// Maximum number of non-overlapping intervals
static int maxNonOverlappingIntervals(int[][]& intervals) {
    if(intervals.length == 0) return 0;

    sort(intervals /* elements of intervals */, [](int[] a, int[] b) {
        return a[1] < b[1];
    });

    int count = 1;
    int end = intervals[0][1];

    for(int i = 1; i < intervals.length; i++) {
        if(intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }

    return count;
}

Fractional Knapsack

Greedy approach: Sort items by value/weight ratio, take items with highest ratio first.

// Fractional Knapsack (not a LeetCode problem, but classic greedy)
class Item {
    public int value, weight;
    public double ratio;
}
double fractionalKnapsack(int W, Item[] items) {
    sort(items /* elements of items */, [](Item a, Item b) {
        return a.ratio > b.ratio;
    });

    double totalValue = 0.0;
    int remainingWeight = W;

    for(auto item : items) {
        if(remainingWeight >= item.weight) {
            totalValue += item.value;
            remainingWeight -= item.weight;
        } else {
            totalValue += item.value * ((double)remainingWeight / item.weight);
            break;
        }
    }

    return totalValue;
}

Greedy on Arrays

Greedy choices on array elements, often with two pointers or sliding window.

// Maximum Subarray (Kadane's Algorithm)
static int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

    for(int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// Best Time to Buy and Sell Stock II
static int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 1; i < prices.size(); i++) {
        if(prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

// Candy - Greedy with sequence tracking
static int candy(int[] ratings) {
    int N = ratings.size();
    int rtn = 1;
    int inc = 1, dec = 0, pre = 1;
    for(int i = 1; i < N; i++) {
        if(ratings[i] >= ratings[i - 1]) {
            dec = 0;
            pre = ratings[i] == ratings[i - 1] ? 1: pre + 1;
            rtn += pre;
            inc = pre;
        } else {
            dec++;
            if(dec == inc) {
                dec++;
            }
            rtn += dec;
            pre = 1;
        }
    }
    return rtn;
}

// Wiggle Subsequence - Greedy with difference tracking
static int wiggleMaxLength(int[] nums) {
    int N = nums.length;
    if(N < 2) return N;
    int prevDiff = nums[1] - nums[0];
    int rtn = prevDiff != 0? 2 : 1;
    for(int i = 2; i < N; i++) {
        int diff = nums[i] - nums[i - 1];
        if((diff > 0 && prevDiff <) ||
            diff < 0 && prevDiff >= 0) {
                rtn++;
                prevDiff = diff;
            }
    }
    return rtn;
}

Greedy on Strings

Greedy choices when processing strings, often with character frequency or ordering.

// Is Subsequence
static boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while(i < s.length() && j < t.length()) {
        if(s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return i == s.length();
}

// Minimum Swaps to Make Strings Equal - Mismatch pairing
static int minimumSwap(String s1, String s2) {
    int xy = 0, yx = 0;
    for(int i = 0; i < s1.length(); i++) {
        if(s1[i] == 'x' && s2[i] == 'y') {
            xy++;
        } else if(s1[i] == 'y' && s2[i] == 'x') {
            yx++;
        }
    }
    if((xy + yx) % 2 == 1) {
        return -1;  // Impossible if odd total mismatches
    }
    return xy / 2 + yx / 2 + xy % 2 + yx % 2;
}

// Construct K Palindrome Strings - Frequency-based greedy
static boolean canConstruct(String s, int k) {
    int right = s.length();
    int occ[26] = {0}
    for(char ch: s) {
        occ[ch - 'a']++;
    }
    int left = 0;
    for(int i = 0; i < 26; i++) {
        if(occ[i] % 2 == 1) {
            left++;
        }
    }
    left = Math.max(left, 1);
    return left <= k && k <= right;
}

Greedy with Sorting

Many greedy problems require sorting first to make optimal choices.

// import java.util.*;
// import java.util.Arrays;
// import java.util.Collections;
// Assign Cookies
static int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);

    int i = 0, j = 0;
    int count = 0;

    while(i < g.length && j < s.size()) {
        if(s[j] >= g[i]) {
            count++;
            i++;
        }
        j++;
    }

    return count;
}

// Array Partition - Maximize sum of minimums
static int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int sum = 0;
    for(int i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }
    return sum;
}

// Maximum Units on a Truck - Fractional knapsack style
static int maximumUnits(int[][]& boxTypes, int truckSize) {
    sort(boxTypes /* elements of boxTypes */, [](auto u, auto v){
        return u[1] > v[1];  // Sort by units per box (descending)
    });
    int remainSize = truckSize;
    int maximumUnits = 0;
    for(auto boxType: boxTypes) {
        if(remainSize == 0) break;
        int cnt = Math.min(remainSize, boxType[0]);
        maximumUnits += cnt boxType[1];
        remainSize -= cnt;
    }
    return maximumUnits;
}

// Minimum Cost to Move Chips - Parity-based greedy
static int minCostToMoveChips(int[] position) {
    int even = 0, odd = 0;
    for(int pos : position) {
        if(pos % 2 == 0) {
            odd++;  // Count even positions
        } else {
            even++;  // Count odd positions
        }
    }
    return Math.min(odd, even);  // Move minority parity to majority
}

// Two City Scheduling - Sort by cost difference
static int twoCitySchedCost(int[][]& costs) {
    sort(costs /* elements of costs */, [](auto u, auto v) {
        return (u[0] - u[1] < v[0] - v[1]);
    });
    int total = 0;
    int N = costs.size() / 2;
    for(int i = 0; i < N; i++) {
        total += costs[i][0] + costs[i + N][1];
    }
    return total;
}

// Find Valid Matrix Given Row and Column Sums - Greedy two pointers
int[][] restoreMatrix(int[] rowSum, int[] colSum) {
    int N = rowSum.size(), M = colSum.size();
    int[][] matrix = new int[N][M];
    int i = 0, j = 0;
    while(i < N && j < M) {
        int v = Math.min(rowSum[i], colSum[j]);
        matrix[i][j] = v;
        rowSum[i] -= v;
        colSum[j] -= v;
        if(rowSum[i] == 0) i++;
        if(colSum[j] == 0) j++;
    }
    return matrix;
}

// Queue Reconstruction by Height
int[][] reconstructQueue(int[][]& people) {
    sort(people /* elements of people */, [](int[] a, int[] b) {
        return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });

    int[][] result;
    for(auto person : people) {
        result.add(result.iterator() + person[1], person);
    }

    return result;
}

Easy Problems

ID Title Link Solution
455 Assign Cookies Link Solution
860 Lemonade Change Link Solution
392 Is Subsequence Link Solution
406 Queue Reconstruction by Height Link Solution
53 Maximum Subarray Link Solution
435 Non-overlapping Intervals Link Solution
452 Minimum Number of Arrows to Burst Balloons Link Solution
561 Array Partition Link Solution
1029 Two City Scheduling Link Solution
122 Best Time to Buy and Sell Stock II Link Solution
1710 Maximum Units on a Truck Link Solution
1217 Minimum Cost to Move Chips to The Same Position Link Solution

Medium Problems

ID Title Link Solution
763 Partition Labels Link -
621 Task Scheduler Link -
435 Non-overlapping Intervals Link Solution
55 Jump Game Link Solution
1094 Car Pooling Link Solution
45 Jump Game II Link Solution
134 Gas Station Link -
1024 Video Stitching Link -
1247 Minimum Swaps to Make Strings Equal Link Solution
1400 Construct K Palindrome Strings Link Solution
1605 Find Valid Matrix Given Row and Column Sums Link Solution
376 Wiggle Subsequence Link Solution

Hard Problems

ID Title Link Solution
135 Candy Link Solution
871 Minimum Number of Refueling Stops Link -
818 Race Car Link -
410 Split Array Largest Sum Link -
420 Strong Password Checker Link -
68 Text Justification Link -
76 Minimum Window Substring Link -
1799 Maximize Score After N Operations Link -

Common Greedy Patterns

1. Interval Problems

  • Sort by end time
  • Always pick the interval that ends earliest
  • Examples: Non-overlapping Intervals, Minimum Arrows to Burst Balloons

2. Two Pointers

  • Use two pointers to make greedy choices
  • Examples: Is Subsequence, Assign Cookies

3. Sorting + Greedy

  • Sort first, then apply greedy strategy
  • Examples: Queue Reconstruction by Height, Two City Scheduling

4. Local Optimization

  • Make best local choice at each step
  • Examples: Best Time to Buy and Sell Stock II, Maximum Subarray

5. Jump Problems

  • Greedy choice: jump as far as possible
  • Examples: Jump Game, Jump Game II

6. Scheduling Problems

  • Sort and schedule optimally
  • Examples: Task Scheduler, Car Pooling

Key Insights

  1. When to use Greedy:
    • Problem has optimal substructure
    • Greedy choice property holds
    • No need to reconsider previous choices
  2. Common Mistakes:
    • Not sorting when needed
    • Wrong sorting criteria
    • Not considering edge cases
    • Assuming greedy always works (need to prove correctness)
  3. Proving Greedy Correctness:
    • Show greedy choice property
    • Show optimal substructure
    • Use exchange argument or contradiction
  • Dynamic Programming (when greedy doesn’t work)
  • Sorting Algorithms
  • Interval Problems
  • Two Pointers
  • Sliding Window

References

More templates