Greedy Algorithms Activity Selection, Knapsack

Greedy in DAA is best learned by connecting the rule to an interview-style problem. Start with the smallest algorithm step, observe the output, and then add one realistic constraint so the concept becomes practical.

The key habit for this lesson is to watch input graph, array, or recurrence as it changes. That makes the topic easier to debug, easier to explain in interviews, and easier to use in real code without memorizing isolated syntax.

What is a Greedy Algorithm?

A greedy algorithm builds a solution step by step by always making the best choice available at the current moment. Once a choice is made, the algorithm usually does not go back and reconsider it. The hope is that a sequence of locally best decisions will lead to a globally optimal solution.

Greedy algorithms are attractive because they are often simple, fast, and easy to implement. However, they are not correct for every optimization problem. A greedy method works only when the structure of the problem supports greedy decisions.

Core Idea

The general pattern of a greedy algorithm is:

Examples of greedy rules include choosing the smallest edge, earliest finishing activity, highest profit-to-weight ratio, or nearest unvisited vertex.

Look at all choices currently available.
Select the one that seems best right now according to some rule.
Commit to that choice permanently.
Reduce the problem and repeat.

When Does Greedy Work?

A greedy algorithm is usually correct only if the problem has the following two properties:

If these properties do not hold, greedy may produce a fast answer, but not necessarily the best one.

Greedy choice property: there exists an optimal solution that begins with the locally optimal choice.
Optimal substructure: after making a correct choice, the remaining problem is still an optimization problem of the same kind.

How to Recognize a Greedy Problem

A problem is a good candidate for a greedy approach if:

If a locally optimal choice can block a much better future solution, greedy is likely unsafe.

you can define a natural local rule such as minimum cost, earliest finish, or maximum ratio,
once a choice is made, it does not need to be changed later,
the problem can be reduced cleanly after each decision,
you can justify correctness using an exchange argument or a cut-style argument.

Greedy Proof Techniques

In exams and interviews, it is not enough to give a greedy rule. You must usually justify why it works. Common proof styles are:

Exchange argument: show that if an optimal solution does not use the greedy choice, it can be modified to include it without becoming worse.
Stays-ahead argument: show that after every step, the greedy solution is at least as good as any other partial solution.
Cut property: used in graph problems like MST, where the best edge across a cut is safe to choose.

Greedy vs Brute Force vs Dynamic Programming

Feature	Greedy	Brute Force	Dynamic Programming
Strategy	Take best local choice	Try all possibilities	Solve overlapping subproblems
Backtracking	No	May or may not	No
Optimality	Only for suitable problems	Yes, if all cases checked	Yes, if recurrence is correct
Typical speed	Usually fast	Usually slow	Moderate to high
Examples	MST, Huffman, activity selection	Subset enumeration	0/1 knapsack, LCS, matrix chain

Common Greedy Problems

Problem	Greedy Rule	Why It Works
Activity Selection	Choose activity with earliest finish time	Leaves maximum room for remaining activities
Fractional Knapsack	Choose highest value/weight ratio first	Fractions are allowed, so local ratio is safe
Huffman Coding	Merge two least frequent symbols	Builds optimal prefix-free code
Kruskal's MST	Take smallest edge that avoids a cycle	Safe by cut property
Prim's MST	Add smallest edge leaving current tree	Safe by cut property
Dijkstra's Algorithm	Finalize nearest unvisited vertex	Works when edge weights are non-negative

Activity Selection Problem

Given a set of activities with start and finish times, choose the maximum number of non-overlapping activities. The correct greedy strategy is to always pick the activity that finishes earliest.

Why not choose the shortest activity or the earliest starting activity? Because those rules can block more activities later. Earliest finish time is the rule that leaves the most room for future selections.

Activity Selection and Fractional Knapsack

import java.util.Arrays;

public class ActivitySelection {

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

        // Sort activities by finish time.
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Integer.compare(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);
    }
}

Activity Selection Problem

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 works greedily because taking part of an item is allowed.
    static double fractionalKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) items[i] = new Item(weights[i], values[i]);

        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

        double totalValue = 0;
        int remaining = capacity;

        for (Item item : items) {
            if (remaining == 0) break;

            if (item.weight <= remaining) {
                totalValue += item.value;
                remaining -= item.weight;
            } else {
                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("Maximum value: %.2f%n",
            fractionalKnapsack(weights, values, capacity));
    }
}

Fractional Knapsack vs 0/1 Knapsack

Fractional knapsack allows taking part of an item, so choosing items by highest value-to-weight ratio is correct. This is a greedy problem.

0/1 knapsack allows either taking the whole item or leaving it. Here, the same greedy rule may fail. That problem is typically solved using dynamic programming.

This is one of the most important examples showing that a small change in problem constraints can completely change the correct algorithmic approach.

Huffman Coding

Huffman coding is a greedy method for building an optimal prefix-free binary code. The idea is simple: repeatedly combine the two least frequent symbols, because rare symbols can safely be placed deeper in the tree.

A priority queue is usually used so that the two minimum-frequency nodes can be selected efficiently at each step.

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 left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        public int compareTo(Node other) {
            return Integer.compare(this.freq, other.freq);
        }

        boolean isLeaf() {
            return left == null && right == null;
        }
    }

    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();
            Node right = pq.poll();
            pq.add(new Node(left.freq + right.freq, left, right));
        }
        return pq.poll();
    }

    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, "");
    }
}

Other Important Greedy Algorithms

Many graph algorithms use greedy ideas:

However, each of these works only under the right conditions. For example, Dijkstra's algorithm fails when negative edge weights are present.

Kruskal's algorithm: repeatedly add the smallest edge that does not form a cycle.
Prim's algorithm: repeatedly add the smallest edge connecting the tree to a new vertex.
Dijkstra's algorithm: repeatedly finalize the vertex with minimum current distance.

Where Greedy Fails

Some problems appear greedy but are not. Common examples include:

Example: for coin values {1, 3, 4} and target 6, greedy gives 4 + 1 + 1 = 3 coins, but the optimal solution is 3 + 3 = 2 coins.

0/1 Knapsack: choosing the highest ratio item first may block the optimal combination.
Coin change with arbitrary denominations: choosing the largest coin first is not always optimal.
Shortest path with negative weights: Dijkstra's greedy decision is no longer safe.

Advantages of Greedy Algorithms

Usually simple to understand and implement.
Often faster than dynamic programming or backtracking.
Commonly uses sorting, heaps, or priority queues, giving efficient running times.
Very useful when an exact optimal solution can be justified by a greedy proof.

Limitations of Greedy Algorithms

A local best choice does not always lead to a global best solution.
Correctness is often problem-specific and must be proved carefully.
A greedy rule that works for one variation of a problem may fail for another.
It is easy to write a greedy solution that looks plausible but is wrong.

Time Complexity Pattern

Many greedy algorithms follow this pattern:

Because of that, their running time is often O(n log n) or O(E log V) in graph problems.

sort the input, or
repeatedly extract the minimum or maximum using a heap or priority queue.

Common Mistakes

Assuming greedy always works because it gives a quick answer.
Using the wrong greedy rule, such as earliest start instead of earliest finish in activity selection.
Applying Dijkstra's algorithm on graphs with negative weights.
Confusing fractional knapsack with 0/1 knapsack.
Writing the algorithm but not proving why the greedy choice is safe.

Greedy vs Dynamic Programming

Feature	Greedy	Dynamic Programming
Decision style	Make the best local choice now	Compare many subproblem results
Revision of choices	No	Indirectly yes, through recurrence
Correctness	Only for suitable problems	Usually guaranteed if recurrence is correct
Speed	Often faster	Often uses more time and memory
Examples	Huffman, MST, activity selection	0/1 knapsack, LCS, edit distance

Key Takeaways

Greedy algorithms make the best local decision at each step.
They work only when the greedy choice is provably safe.
Greedy choice property and optimal substructure are the main signals.
Classic greedy problems include activity selection, fractional knapsack, Huffman coding, MST, and Dijkstra's algorithm.
Always ask: does the local best choice guarantee a global optimum?

Applied guide for Greedy

Use Greedy when the program needs a clear answer to a specific problem, not because the keyword looks familiar. In a real DAA task, first name the input, then name the transformation, then name the output. This small discipline shows whether the topic is being used correctly or only copied from an example.

A reliable practice flow is: create the smallest working algorithm step, add one normal case, add one edge case such as counterexamples that break the greedy choice, and then confirm the result with trace table and complexity count. If the result surprises you, reduce the code until the behavior is visible again.

The most common trap here is choosing the local best step without proving it stays optimal. Avoid it by writing one sentence before the code that explains why Greedy is the right choice. After the code runs, verify the lesson by doing this: state the greedy-choice property.

Identify the exact problem solved by Greedy.
Trace input graph, array, or recurrence before and after the main operation.
Keep one intentionally broken version and explain the fix.
Connect the example to an interview-style problem so the idea feels concrete.

Key Takeaways

I can explain where Greedy fits inside an interview-style problem.
I can point to the exact input graph, array, or recurrence affected by this topic.
I tested a normal case and an edge case involving counterexamples that break the greedy choice.
I verified the result with trace table and complexity count instead of assuming it worked.
I can describe the main mistake: choosing the local best step without proving it stays optimal.

Common Mistakes to Avoid

WRONG Choosing the local best step without proving it stays optimal.

RIGHT Write the expected behavior first, then make the example prove it.

A one-line expectation turns the code from copied syntax into a testable idea.

WRONG Practicing only the perfect input.

RIGHT Also test counterexamples that break the greedy choice before considering the lesson complete.

The edge case is where most interview follow-up questions begin.

WRONG Looking only at the final output.

RIGHT Trace input graph, array, or recurrence through each important step.

Tracing makes debugging faster because you can see the first incorrect state.

Practice Tasks

Build one small algorithm step that demonstrates Greedy in an interview-style problem.
Change the example to include counterexamples that break the greedy choice and record the difference.
Break the example by deliberately choosing the local best step without proving it stays optimal, then write the corrected version.
Explain the finished example in five bullet points: input, operation, output, failure case, and verification.

Frequently Asked Questions

When should I use Greedy?

Use it when the problem matches the behavior shown in the example and when the result can be verified through trace table and complexity count.

How do I avoid mistakes in Greedy?

Start with a tiny case, then test counterexamples that break the greedy choice. The main warning sign is choosing the local best step without proving it stays optimal.

How can I revise Greedy quickly?

Trace input graph, array, or recurrence, predict the result, run the example, and compare your prediction with the actual output.

Previous Next

Greedy Algorithms Activity Selection, Knapsack