💰 Greedy Algorithm – Comprehensive Study Guide

A **Greedy Algorithm** is an approach used to solve **optimization problems** by making the **locally optimal choice at each step** with the hope of reaching the **globally optimal solution**.

⚡ Why Use Greedy Algorithms?

• ✅ **Faster than Dynamic Programming (O(n log n) or O(n)).**
• 🚀 **Used in scheduling, graph problems, and resource allocation.**
• 📡 **Provides approximate solutions for NP-Hard problems.**
• 🔄 **Simple and easy to implement.**

📌 How Does the Greedy Approach Work?

The greedy approach **works step by step**, making the best immediate choice. However, it **does not always guarantee an optimal solution** for all problems.

✅ **Conditions for a Problem to be Solved Using Greedy**

• 📌 **Greedy Choice Property** – An optimal solution can be reached by making local choices.
• 📌 **Optimal Substructure** – The optimal solution to a problem contains optimal solutions to its subproblems.

🔥 Common Greedy Algorithm Problems & Their Solutions

📌 **1. Activity Selection Problem (O(n log n))**

Find the maximum number of activities that can be done by one person.

                struct Activity {
                    int start, end;
                };
            
                bool cmp(Activity a, Activity b) {
                    return a.end < b.end; // Sort by finish time
                }
            
                int activitySelection(vector& activities) {
                    sort(activities.begin(), activities.end(), cmp);
                    int count = 1, lastEnd = activities[0].end;
                    
                    for (int i = 1; i < activities.size(); i++) {
                        if (activities[i].start >= lastEnd) {
                            count++;
                            lastEnd = activities[i].end;
                        }
                    }
                    return count;
                }
                

📌 **2. Fractional Knapsack Problem (O(n log n))**

Choose items with maximum value-to-weight ratio.

                struct Item {
                    int weight, value;
                };
            
                bool cmp(Item a, Item b) {
                    return (double)a.value / a.weight > (double)b.value / b.weight;
                }
            
                double fractionalKnapsack(vector& items, int W) {
                    sort(items.begin(), items.end(), cmp);
                    double maxValue = 0.0;
                    
                    for (auto item : items) {
                        if (W >= item.weight) {
                            maxValue += item.value;
                            W -= item.weight;
                        } else {
                            maxValue += item.value * ((double)W / item.weight);
                            break;
                        }
                    }
                    return maxValue;
                }
                

📌 **3. Huffman Coding (O(n log n))**

Build an optimal prefix code for text compression.

                struct Node {
                    char ch;
                    int freq;
                    Node *left, *right;
                };
            
                struct Compare {
                    bool operator()(Node* a, Node* b) {
                        return a->freq > b->freq; // Min-heap based on frequency
                    }
                };
            
                void huffmanCoding(vector>& data) {
                    priority_queue, Compare> pq;
            
                    for (auto item : data) pq.push(new Node{item.first, item.second, NULL, NULL});
                    
                    while (pq.size() > 1) {
                        Node *left = pq.top(); pq.pop();
                        Node *right = pq.top(); pq.pop();
                        pq.push(new Node{'\0', left->freq + right->freq, left, right});
                    }
            
                    // The remaining node is the root of Huffman Tree
                }
                

⚖️ Greedy vs Dynamic Programming

⏳ Time Complexity Analysis

• ✅ **Best Case:** O(n log n) (Sorting-based Greedy problems).
• ⚡ **Worst Case:** O(n²) (In some graph-based problems).

🌍 Real-World Applications of Greedy Algorithm

• 📡 **Network Routing (Prim’s MST Algorithm).**
• 🎥 **Video Compression (Huffman Coding).**
• 🛒 **Warehouse Optimization (Fractional Knapsack).**
• 🎭 **Task Scheduling (Activity Selection).**

🔗 Next Topics

• 🌲 Prim’s Algorithm (MST)
• 📡 Kruskal’s Algorithm (MST)
• 📜 Huffman Coding