Skip to main content

Greedy Algorithms

Greedy Algorithms: Making the Best Local Choice

Many computer science students fundamentally confuse Greedy Algorithms, Dynamic Programming, and Backtracking. This happens because developers use all three techniques to solve optimization problems (finding the maximum profit, minimum cost, or shortest path). However, the way they approach the solution differs entirely.

Technique Decision Making Process
Greedy Makes the absolute best choice available right now, ignoring future consequences.
Dynamic Programming Evaluates all possibilities, caches the results, and combines them to find the true optimal answer.
Backtracking Tries every single path. If a path fails, it undoes the decision and explores a different route.

What Exactly is a Greedy Algorithm?

A Greedy Algorithm makes a localized, immediate decision. It never looks back, and it never revisits a previous choice.

Real-Life Example: Imagine you need to give exactly $880 in physical cash using standard currency notes ($500, $200, $100, $50, $20, $10). A greedy algorithm approaches this by constantly grabbing the largest note possible that fits into the remaining balance:

  • Take a $500 note. (Remaining: $380)
  • Take a $200 note. (Remaining: $180)
  • Take a $100 note. (Remaining: $80)
  • Take a $50 note. (Remaining: $30)
  • Take a $20 note. (Remaining: $10)
  • Take a $10 note. (Done.)

We call this "Greedy" because the algorithm exhibits an aggressive appetite for the immediate maximum benefit. It never stops to calculate a holistic future plan.

When Does the Greedy Approach Actually Work?

You cannot use a Greedy strategy on every problem. It only yields the mathematically correct answer if the problem satisfies two strict properties:

  • 1. The Greedy Choice Property: A local optimum (the best choice right now) perfectly leads to the global optimum (the overall correct answer).
  • 2. Optimal Substructure: You can build the optimal solution for the massive problem strictly by solving its smaller subproblems perfectly.

The Generic Greedy Code Structure

Almost every single Greedy problem in an interview starts with one specific action: Sorting the data. If you sort the data optimally, the greedy selection becomes incredibly simple.

// The universal framework for a Greedy Algorithm
Sort(Data);

for(each item in Data) {
    if(item fits current constraints) {
        select(item);
    }
}

Problem 1: Activity Selection

This is arguably the most famous Greedy problem taught in computer science.

Problem Statement: You possess a single meeting room and a list of requested meetings. Each meeting has a distinct start and end time. You must schedule the absolute maximum number of non-overlapping meetings into that room.

The Wrong Approaches

  • Choosing the shortest duration meeting? Incorrect. A short 1-hour meeting might sit perfectly in the middle of the day, blocking a 3-hour morning meeting and a 4-hour afternoon meeting.
  • Choosing the earliest starting meeting? Incorrect. A meeting that starts at 8:00 AM but lasts for 10 hours will instantly ruin the rest of your schedule.

The Correct Greedy Choice

You must always choose the activity with the earliest finish time. Doing this explicitly leaves the maximum amount of open room on your calendar to schedule future events.

The Algorithm ($O(N \log N)$)

Step 1: Sort all activities by their finish times.
Step 2: Select the first activity unconditionally.
Step 3: For every subsequent activity, check if its start time occurs after or at the exact same time as your previous activity's finish time. If it does, schedule it.

#include <stdio.h>

struct Activity {
    int start;
    int finish;
};

int main() {
    // Pre-sorted by finish time for demonstration
    struct Activity arr[] = {
        {1,2}, {3,4}, {0,6}, {5,7}, {8,9}, {5,9}
    };
    int n = 6;
    int count = 1; // Always select the first sorted item
    int lastFinish = arr[0].finish;

    printf("Selected Activities:\n");
    printf("[%d, %d]\n", arr[0].start, lastFinish);

    for(int i = 1; i < n; i++) {
        // If this activity starts after the previous one finishes
        if(arr[i].start >= lastFinish) {
            count++;
            lastFinish = arr[i].finish; // Update our timeline
            printf("[%d, %d]\n", arr[i].start, arr[i].finish);
        }
    }

    printf("Total Activities Scheduled = %d\n", count);
    return 0;
}

Problem 2: Job Scheduling with Deadlines

Problem Statement: You receive a list of jobs. Every job requires exactly 1 unit of time to complete. Each job has a strict deadline and a specific profit attached to it. You must select jobs to maximize your total profit.

The Greedy Strategy

Always prioritize the jobs that pay the most. Sort the jobs descending by profit. Then, to maximize your calendar efficiency, schedule that high-paying job in the latest possible time slot right before its deadline. This leaves your early time slots open for jobs with shorter deadlines.

#include <stdio.h>

struct Job {
    char id;
    int deadline;
    int profit;
};

int main() {
    // Pre-sorted descending by profit
    struct Job jobs[] = {
        {'A', 2, 100}, {'C', 2, 27}, {'D', 1, 25}, {'B', 1, 19}, {'E', 3, 15}
    };

    int slots[10] = {0}; // Calendar array tracking open hours
    int totalProfit = 0;

    for(int i = 0; i < 5; i++) {
        // Look backwards from the deadline to find the latest open slot
        for(int j = jobs[i].deadline; j > 0; j--) {
            if(slots[j] == 0) {
                slots[j] = 1; // Mark the time slot as booked
                totalProfit += jobs[i].profit;
                break; // Move to the next job
            }
        }
    }

    printf("Maximum Profit Attained = %d\n", totalProfit);
    return 0;
}

Problem 3: Huffman Coding

Software uses Huffman Coding daily to compress data formats like ZIP, RAR, JPEG, and MP3 files. In standard text encoding, every character uses exactly 8 bits. This wastes tremendous space. Huffman coding compresses data by assigning extremely short binary codes to characters that appear frequently, and longer codes to rare characters.

The Greedy Strategy ($O(N \log N)$)

To build the optimal compression tree, we utilize a Min-Heap Priority Queue. At every single step, the algorithm aggressively targets the two smallest frequencies available. It extracts them, combines their sums to build a parent node, and drops that new node back into the queue. By constantly targeting the smallest values, frequent characters inherently stay near the top of the tree, yielding the shortest encoded bitpaths.

Greedy Pattern Recognition Checklist

How do you know an interview problem requires a Greedy algorithm? Check if it asks for:

  • Maximum Activities or Jobs
  • Maximum Profit margins
  • Minimum Cost or Platform requirements
  • Optimal Merging or File Compressions

Ask yourself: "Can I sort this data, confidently make the absolute best localized choice right now, and never need to undo that choice?" If yes, write a Greedy solution.

The Ultimate Interview Cheat Sheet

Memorize these absolute best local choices for standard coding questions:

Problem Name The Correct Greedy Choice
Activity Selection Sort by Earliest Finish Time
Fractional Knapsack Sort descending by Profit-to-Weight Ratio
Job Scheduling Sort descending by Highest Profit
Huffman Coding Repeatedly merge the Two Smallest Frequencies
Minimum Platforms Sort by Earliest Departure Time
Merge Intervals Sort by Earliest Start Time
Jump Game Track the Farthest Absolute Reachable Index

The Golden Rule of Greedy Algorithms: Sort the data first. Pick the best available choice. Never reconsider it. Loop until completion.

Comments

Post a Comment