owlingcode

What is a Greedy Algorithm?

A greedy algorithm makes the best choice at each step without considering future consequences. The key insight is that local optimality can sometimes lead to global optimality.

Activity Selection Problem

Select the maximum number of activities that don't overlap:

#include <vector>
#include <algorithm>

struct Activity {
    int start, finish;
    int id;
};

int activitySelection(vector<Activity>& activities) {
    // Sort by finish time (greedy choice)
    sort(activities.begin(), activities.end(), 
         [](const Activity& a, const Activity& b) {
             return a.finish < b.finish;
         });
    
    int count = 1; // First activity is always selected
    int lastFinish = activities[0].finish;
    
    cout << "Selected activities: " << activities[0].id << " ";
    
    for (int i = 1; i < activities.size(); i++) {
        // If this activity starts after the last selected activity finishes
        if (activities[i].start >= lastFinish) {
            cout << activities[i].id << " ";
            lastFinish = activities[i].finish;
            count++;
        }
    }
    cout << endl;
    
    return count;
}

int main() {
    vector<Activity> activities = {
        {1, 4, 1}, {3, 5, 2}, {0, 6, 3}, 
        {5, 7, 4}, {3, 9, 5}, {5, 9, 6}, 
        {6, 10, 7}, {8, 11, 8}, {8, 12, 9}, 
        {2, 14, 10}, {12, 16, 11}
    };
    
    int maxActivities = activitySelection(activities);
    cout << "Maximum activities: " << maxActivities << endl;
    
    return 0;
}
                    

Fractional Knapsack Problem

Maximize value in a knapsack where items can be broken into fractions:

#include <vector>
#include <algorithm>

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

double fractionalKnapsack(vector<Item>& items, int capacity) {
    // Sort by value-to-weight ratio (greedy choice)
    sort(items.begin(), items.end(), 
         [](const Item& a, const Item& b) {
             return a.ratio > b.ratio;
         });
    
    double totalValue = 0.0;
    int currentWeight = 0;
    
    for (const Item& item : items) {
        if (currentWeight + item.weight <= capacity) {
            // Take the whole item
            currentWeight += item.weight;
            totalValue += item.value;
            cout << "Take full item: weight=" << item.weight 
                 << ", value=" << item.value << endl;
        } else {
            // Take fraction of the item
            int remainingCapacity = capacity - currentWeight;
            double fraction = (double)remainingCapacity / item.weight;
            totalValue += item.value * fraction;
            cout << "Take " << fraction << " of item: weight=" 
                 << item.weight << ", value=" << item.value << endl;
            break;
        }
    }
    
    return totalValue;
}

int main() {
    vector<Item> items = {
        Item(10, 60), Item(20, 100), Item(30, 120)
    };
    int capacity = 50;
    
    double maxValue = fractionalKnapsack(items, capacity);
    cout << "Maximum value: " << maxValue << endl;
    
    return 0;
}
                    

Job Scheduling with Deadlines

Schedule jobs to maximize profit while meeting deadlines:

#include <vector>
#include <algorithm>

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

vector<char> jobScheduling(vector<Job>& jobs) {
    // Sort by profit in descending order (greedy choice)
    sort(jobs.begin(), jobs.end(), 
         [](const Job& a, const Job& b) {
             return a.profit > b.profit;
         });
    
    // Find maximum deadline
    int maxDeadline = 0;
    for (const Job& job : jobs) {
        maxDeadline = max(maxDeadline, job.deadline);
    }
    
    // Create a schedule array
    vector<char> schedule(maxDeadline, '0');
    vector<bool> slot(maxDeadline, false);
    
    int totalProfit = 0;
    
    for (const Job& job : jobs) {
        // Find a free slot for this job (from deadline-1 to 0)
        for (int j = min(maxDeadline, job.deadline) - 1; j >= 0; j--) {
            if (!slot[j]) {
                slot[j] = true;
                schedule[j] = job.id;
                totalProfit += job.profit;
                break;
            }
        }
    }
    
    cout << "Total profit: " << totalProfit << endl;
    return schedule;
}

int main() {
    vector<Job> jobs = {
        {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
        {'d', 1, 25}, {'e', 3, 15}
    };
    
    vector<char> schedule = jobScheduling(jobs);
    
    cout << "Job sequence: ";
    for (char job : schedule) {
        if (job != '0') {
            cout << job << " ";
        }
    }
    cout << endl;
    
    return 0;
}
                    

Coin Change (Greedy Approach)

Find minimum coins needed for a given amount (works for certain coin systems):

#include <vector>

vector<int> coinChangeGreedy(vector<int>& coins, int amount) {
    vector<int> result;
    
    // Sort coins in descending order
    sort(coins.begin(), coins.end(), greater<int>());
    
    for (int coin : coins) {
        while (amount >= coin) {
            result.push_back(coin);
            amount -= coin;
        }
    }
    
    if (amount == 0) {
        return result;
    } else {
        return {}; // No solution possible
    }
}

int main() {
    // This works for canonical coin systems (like US coins: 25, 10, 5, 1)
    vector<int> coins = {25, 10, 5, 1};
    int amount = 67;
    
    vector<int> result = coinChangeGreedy(coins, amount);
    
    if (!result.empty()) {
        cout << "Coins needed: ";
        for (int coin : result) {
            cout << coin << " ";
        }
        cout << endl;
        cout << "Total coins: " << result.size() << endl;
    } else {
        cout << "No solution found" << endl;
    }
    
    return 0;
}
                    

Huffman Coding

Create optimal prefix-free codes for data compression:

#include <queue>
#include <unordered_map>

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    HuffmanNode(int f) : ch(0), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq; // Min heap
    }
};

void generateCodes(HuffmanNode* root, string code, unordered_map<char, string>& codes) {
    if (!root) return;
    
    if (root->ch != 0) { // Leaf node
        codes[root->ch] = code.empty() ? "0" : code;
        return;
    }
    
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

unordered_map<char, string> huffmanCoding(const string& text) {
    // Count frequencies
    unordered_map<char, int> freq;
    for (char c : text) {
        freq[c]++;
    }
    
    // Create priority queue
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
    for (auto& pair : freq) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }
    
    // Build Huffman tree
    while (pq.size() > 1) {
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* left = pq.top(); pq.pop();
        
        HuffmanNode* merged = new HuffmanNode(left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        
        pq.push(merged);
    }
    
    // Generate codes
    unordered_map<char, string> codes;
    generateCodes(pq.top(), "", codes);
    
    return codes;
}
                    

When Greedy Works vs When It Doesn't

Greedy Algorithm Template

// General greedy algorithm structure
template<typename T>
Solution greedyAlgorithm(vector<T>& elements) {
    // 1. Sort elements by greedy criteria
    sort(elements.begin(), elements.end(), greedyComparator);
    
    Solution solution;
    
    // 2. Make greedy choices
    for (const T& element : elements) {
        if (isSafe(solution, element)) {
            solution.add(element);
        }
    }
    
    return solution;
}