Greedy Algorithms

1. Introduction: Living in the Moment

Imagine you are at a buffet. You want to eat as much high-protein food as possible. You don't map out a complex 5-course plan or calculate overlapping nutritional subproblems (Dynamic Programming). You just look at the table, find the single most protein-dense item, and put it on your plate. You repeat this until your plate is full.

This is a Greedy Algorithm. At every single step, it makes the locally optimal choice—the choice that looks best right now—with the hope that these local choices will magically add up to the global optimal solution.

Greedy algorithms are blazing fast (usually $O(N \log N)$ due to sorting) and easy to write. The hard part isn't writing the code; the hard part is proving mathematically that a greedy approach actually works for the specific problem at hand.

2. Core Concept: When Does Greedy Work?

A problem can be solved with a Greedy algorithm if it has two properties:

1. Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum. (We never have to reconsider or backtrack on our past choices).
2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to the sub-problems. (Similar to DP).

The Warning: Greedy algorithms fail constantly. In the "Coin Change" problem, if coins are [1, 5, 10, 25], Greedy works perfectly. To make 30 cents, you pick 25, then 5. (2 coins). But if the coins are [1, 15, 25], and you want 30 cents, Greedy picks 25, then five 1s. (6 coins). The true optimal is picking two 15s (2 coins). Greedy failed! You must always test a greedy idea against counter-examples before writing code in an interview.

3. Beginner Code Example: Activity Selection (Interval Scheduling)

Problem Statement: You are given $n$ activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

The Greedy Choice: We want to fit as many activities as possible. To do this, we should always pick the activity that ends the earliest, because that leaves the maximum amount of free time for subsequent activities!

import java.util.Arrays;

public class ActivitySelection {
    public static int maxActivities(int[][] activities) {
        // activities[i] = [startTime, endTime]
        
        // 1. Sort activities strictly by their FINISH time
        Arrays.sort(activities, (a, b) -> Integer.compare(a[1], b[1]));
        
        int count = 0;
        int lastFinishTime = -1;
        
        // 2. Iterate through sorted activities
        for (int[] activity : activities) {
            int start = activity[0];
            int finish = activity[1];
            
            // If this activity starts AFTER the last one finished, we can do it!
            if (start >= lastFinishTime) {
                count++;
                lastFinishTime = finish; // Update our schedule
            }
        }
        
        return count;
    }
}

Complexity Analysis:

• Time Complexity: $O(N \log N)$ for sorting the array. The linear scan takes $O(N)$.
• Space Complexity: $O(1)$ (or $O(\log N)$ depending on the language's built-in sorting algorithm overhead).

4. Intermediate Code Example: Fractional Knapsack

Problem Statement: You are given weights and values of $N$ items. You have a knapsack of capacity $W$. You want to get the maximum total value. Unlike the 0/1 Knapsack DP problem, you CAN break items into fractions. (e.g., You can take 50% of the gold dust for 50% of its value).

The Greedy Choice: We want the most bang for our buck. We should calculate the Value-to-Weight ratio for every item. We sort them descending by this ratio. We take as much of the highest ratio item as possible, then move to the next, until the bag is full.

import java.util.Arrays;

public class FractionalKnapsack {
    static class Item {
        int weight;
        int value;
        double ratio;
        
        Item(int w, int v) {
            weight = w;
            value = v;
            ratio = (double) v / w;
        }
    }
    
    public static double getMaxValue(int W, Item[] items) {
        // Sort by Value/Weight ratio in DESCENDING order
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));
        
        double totalValue = 0.0;
        
        for (Item item : items) {
            if (W == 0) break; // Bag is full
            
            if (item.weight <= W) {
                // We can take the whole item
                W -= item.weight;
                totalValue += item.value;
            } else {
                // We can only take a fraction of the item to fill the remaining space
                totalValue += item.ratio * W;
                W = 0; // Bag is now completely full
            }
        }
        
        return totalValue;
    }
}

5. Advanced Code Example: Task Scheduler (Math/Greedy)

Problem Statement: (LeetCode 621) You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals. Return the minimum number of intervals required to complete all tasks.

The Insight: The bottleneck is the task that appears the most frequently! If Task A appears 5 times, and n=2, we MUST schedule it like this: A _ _ A _ _ A _ _ A _ _ A. The "empty slots" (_) can be filled with other tasks for free! We only need extra time if the total number of tasks exceeds the size of this foundational framework.

import java.util.Arrays;

public class TaskScheduler {
    public int leastInterval(char[] tasks, int n) {
        // 1. Count frequencies
        int[] frequencies = new int[26];
        for (char task : tasks) {
            frequencies[task - 'A']++;
        }
        
        // 2. Sort frequencies (Ascending)
        Arrays.sort(frequencies);
        
        // The most frequent task is at the end
        int maxFreq = frequencies[25];
        
        // 3. Calculate the maximum possible idle slots
        // -1 because the last execution doesn't need to be followed by idle time
        int idleSlots = (maxFreq - 1) * n; 
        
        // 4. Fill the idle slots with the remaining tasks
        for (int i = 24; i >= 0; i--) {
            // We can't put a task in more slots than (maxFreq - 1) 
            // without violating the cooling rule at the very end.
            idleSlots -= Math.min(maxFreq - 1, frequencies[i]);
        }
        
        // 5. If idleSlots is negative, it means we had so many other tasks 
        // that we never had to wait at all!
        idleSlots = Math.max(0, idleSlots);
        
        // Total time is the number of actual tasks + the forced idle time
        return tasks.length + idleSlots;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ to count frequencies. The sort is $O(1)$ because the array is strictly size 26.
• Space Complexity: $O(1)$ for the frequency array.

6. Common Mistakes Beginners Make

1. Blindly applying Greedy without proving it

   • The Mistake: Writing a Greedy solution for 0/1 Knapsack or Longest Increasing Subsequence.
   • Why it's wrong: The interviewer will immediately provide a counter-example that breaks your logic.
   • The Fix: Before coding, actively try to construct a malicious test case that breaks your greedy choice. If you can break it, you must switch to Dynamic Programming.

2. Sorting by the wrong variable in Intervals

   • The Mistake: Sorting activities by their Start Time or Duration.
   • Why it's wrong: An activity might start early but last for 10 hours, blocking everything else. Always sort by Finish Time when you want to maximize the count of non-overlapping intervals.

3. Using a - b for Double Comparators

   • The Mistake: Arrays.sort(items, (a, b) -> (int)(b.ratio - a.ratio));
   • Why it's wrong: Casting to int truncates decimals. If a = 1.1 and b = 1.9, 1.9 - 1.1 = 0.8. Cast to int becomes 0 (saying they are equal!).
   • The Fix: Always use Double.compare(b.ratio, a.ratio).

7. Interview Q&A

Q1: What's the fundamental difference between Greedy and DP? Answer: Greedy makes a local optimum choice and never looks back. DP considers all possible choices, explores their outcomes, and picks the global optimum. Greedy is faster but only mathematically valid for certain problems. DP is universally valid but slower.

Q2: How do I prove a Greedy algorithm is correct in an interview? Answer: Use an "Exchange Argument". Assume there is an optimal solution that differs from your Greedy solution. Prove that if you "exchange" a piece of that optimal solution for your Greedy choice, the overall result stays the same or improves. This proves the Greedy choice is never worse.

Q3: Does Huffman Coding use Greedy? Answer: Yes! Huffman Coding (used for file compression) builds its tree by greedily combining the two nodes with the lowest frequencies at every step. It mathematically guarantees the optimal prefix-free binary tree.

8. Practice Problems

1. Assign Cookies (LeetCode 455)
   • Goal: The absolute simplest greedy problem. Sort both arrays!
2. Maximum Units on a Truck (LeetCode 1710)
   • Goal: A direct implementation of Fractional Knapsack.
3. Jump Game (LeetCode 55)
   • Hint: Greedily keep track of the maximum reachable index. If your current index exceeds the max reachable index, you lose!

9. Summary

• The Core Idea: Pick the best immediate option. Do not backtrack.
• The Prerequisite: You almost always have to Sort the input array first to establish a greedy hierarchy (e.g., by finish time, by cost, by value-ratio).
• The Danger: Always attempt to break your own greedy logic with a counter-example. If choices have complex downstream consequences, you need DP.