Greedy Algorithms

What is a Greedy Algorithm?

A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum. It never reconsiders past choices. Greedy works when the problem has:

Greedy choice property â€” a globally optimal solution can be reached by making locally optimal choices.
Optimal substructure â€” optimal solution contains optimal solutions to subproblems.

Important: Greedy doesn't always give the optimal solution. For example, the coin change problem with arbitrary denominations requires DP, not greedy.

Activity Selection Problem

Given n activities with start and finish times, select the maximum number of non-overlapping activities. Greedy strategy: always pick the activity that finishes earliest.

Activity Selection and Fractional Knapsack

import java.util.Arrays;

public class ActivitySelection {

    static void selectActivities(int[] start, int[] finish) {
        int n = start.length;

        // Sort by finish time (greedy choice)
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> finish[a] - finish[b]);

        System.out.println("Selected activities:");
        int lastFinish = -1;
        int count = 0;

        for (int i : idx) {
            if (start[i] >= lastFinish) {
                System.out.println("  Activity " + i +
                    " [" + start[i] + ", " + finish[i] + "]");
                lastFinish = finish[i];
                count++;
            }
        }
        System.out.println("Total: " + count + " activities");
    }

    public static void main(String[] args) {
        int[] start  = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        selectActivities(start, finish);
        // Activities: 0[1,2], 1[3,4], 3[5,7], 4[8,9] â†’ 4 activities
    }
}

import java.util.Arrays;

public class FractionalKnapsack {

    static class Item {
        int weight, value;
        double ratio;
        Item(int w, int v) { weight = w; value = v; ratio = (double)v / w; }
    }

    // Fractional Knapsack â€” greedy by value/weight ratio
    // O(n log n) â€” sort by ratio, then greedily fill
    static double fractionalKnapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) items[i] = new Item(weights[i], values[i]);

        // Sort by value/weight ratio descending
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

        double totalValue = 0;
        int remaining = W;

        for (Item item : items) {
            if (remaining == 0) break;
            if (item.weight <= remaining) {
                totalValue += item.value;
                remaining -= item.weight;
            } else {
                // Take fraction of item
                totalValue += item.ratio * remaining;
                remaining = 0;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values  = {60, 100, 120};
        int capacity  = 50;
        System.out.printf("Max value: %.2f%n",
            fractionalKnapsack(weights, values, capacity));  // 240.00
    }
}

Huffman Coding â€” Greedy Compression

Huffman coding assigns shorter binary codes to more frequent characters and longer codes to less frequent ones. It is a greedy algorithm that builds an optimal prefix-free code.

Huffman Coding

import java.util.PriorityQueue;

public class HuffmanCoding {

    static class Node implements Comparable<Node> {
        char ch;
        int freq;
        Node left, right;

        Node(char ch, int freq) { this.ch = ch; this.freq = freq; }
        Node(int freq, Node l, Node r) { this.freq = freq; left = l; right = r; }

        public int compareTo(Node other) { return this.freq - other.freq; }
        boolean isLeaf() { return left == null && right == null; }
    }

    // Build Huffman tree â€” O(n log n)
    static Node buildTree(char[] chars, int[] freqs) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < chars.length; i++)
            pq.add(new Node(chars[i], freqs[i]));

        while (pq.size() > 1) {
            Node left  = pq.poll();  // smallest frequency
            Node right = pq.poll();  // second smallest
            pq.add(new Node(left.freq + right.freq, left, right));
        }
        return pq.poll();  // root of Huffman tree
    }

    // Print codes â€” traverse tree, 0 for left, 1 for right
    static void printCodes(Node root, String code) {
        if (root == null) return;
        if (root.isLeaf()) {
            System.out.printf("  '%c' (freq=%d): %s%n", root.ch, root.freq, code);
            return;
        }
        printCodes(root.left,  code + "0");
        printCodes(root.right, code + "1");
    }

    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
        int[]  freqs = { 5,   9,  12,  13,  16,  45};

        Node root = buildTree(chars, freqs);
        System.out.println("Huffman Codes:");
        printCodes(root, "");
    }
}

/*
 * Output (one possible encoding):
 * 'f' (freq=45): 0        â† most frequent â†’ shortest code
 * 'c' (freq=12): 100
 * 'd' (freq=13): 101
 * 'a' (freq=5):  1100
 * 'b' (freq=9):  1101
 * 'e' (freq=16): 111
 *
 * Fixed-length encoding would need 3 bits per char (6 chars = 2Â³)
 * Huffman encoding saves ~45% space for this distribution
 */

Greedy vs Dynamic Programming

Feature	Greedy	Dynamic Programming
Approach	Local optimal choice	All subproblems solved
Correctness	Not always optimal	Always optimal
Efficiency	Usually faster	More time/space
Examples	Activity selection, Dijkstra, Huffman	Knapsack, LCS, Floyd-Warshall

Greedy Algorithms

What is a Greedy Algorithm?

Activity Selection Problem

Huffman Coding â€” Greedy Compression

Greedy vs Dynamic Programming

Ready to Level Up Your Skills?