greedy_patterns.cpp

/*
Greedy Algorithm Patterns
Mathematical Foundation: Optimal substructure with greedy choice property
Prove: Greedy choice + optimal subproblem = optimal solution
Exchange argument: Show greedy is at least as good as any other choice
Applications: Scheduling, spanning trees, Huffman coding
*/

#include <bits/stdc++.h>
using namespace std;

// Activity Selection Problem
// LeetCode: 435. Non-overlapping Intervals
// https://leetcode.com/problems/non-overlapping-intervals/
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return a[1] < b[1]; // Sort by end time
    });
    
    int count = 0, lastEnd = INT_MIN;
    for (auto& iv : intervals) {
        if (iv[0] >= lastEnd) {
            lastEnd = iv[1];
            count++;
        }
    }
    return intervals.size() - count;
}

// Jump Game
// LeetCode: 55. Jump Game
// https://leetcode.com/problems/jump-game/
bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i > maxReach) return false;
        maxReach = max(maxReach, i + nums[i]);
    }
    return true;
}

// Jump Game II (Minimum Jumps)
// LeetCode: 45. Jump Game II
// https://leetcode.com/problems/jump-game-ii/
int jump(vector<int>& nums) {
    int jumps = 0, curEnd = 0, curFarthest = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        curFarthest = max(curFarthest, i + nums[i]);
        if (i == curEnd) {
            jumps++;
            curEnd = curFarthest;
        }
    }
    return jumps;
}

// Gas Station
// LeetCode: 134. Gas Station
// https://leetcode.com/problems/gas-station/
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.size(); i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {
            tank = 0;
            start = i + 1;
        }
    }
    return total >= 0 ? start : -1;
}

// Best Time to Buy and Sell Stock II
// LeetCode: 122. Best Time to Buy and Sell Stock II
// https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
int maxProfit(vector<int>& prices) {
    int profit = 0;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

// Candy Distribution
// LeetCode: 135. Candy
// https://leetcode.com/problems/candy/
int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);
    
    // Left to right pass
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    
    // Right to left pass
    for (int i = n-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            candies[i] = max(candies[i], candies[i+1] + 1);
        }
    }
    
    return accumulate(candies.begin(), candies.end(), 0);
}

// Fractional Knapsack
// Classical Problem - Greedy approach
double fractionalKnapsack(vector<pair<int,int>>& items, int W) {
    // items[i] = {value, weight}
    sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return (double)a.first/a.second > (double)b.first/b.second;
    });
    
    double maxValue = 0;
    for (auto& item : items) {
        if (W >= item.second) {
            maxValue += item.first;
            W -= item.second;
        } else {
            maxValue += (double)item.first * W / item.second;
            break;
        }
    }
    return maxValue;
}

// Minimum Number of Arrows to Burst Balloons
// LeetCode: 452. Minimum Number of Arrows to Burst Balloons
// https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [](auto& a, auto& b) {
        return a[1] < b[1];
    });
    
    int arrows = 1, end = points[0][1];
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] > end) {
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
}

// Queue Reconstruction by Height
// LeetCode: 406. Queue Reconstruction by Height
// https://leetcode.com/problems/queue-reconstruction-by-height/
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](auto& a, auto& b) {
        return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });
    
    vector<vector<int>> result;
    for (auto& person : people) {
        result.insert(result.begin() + person[1], person);
    }
    return result;
}

// Monotonic Stack - Remove K Digits
// LeetCode: 402. Remove K Digits
// https://leetcode.com/problems/remove-k-digits/
string removeKdigits(string num, int k) {
    string result;
    for (char digit : num) {
        while (k > 0 && !result.empty() && result.back() > digit) {
            result.pop_back();
            k--;
        }
        result.push_back(digit);
    }
    
    // Remove remaining digits from the end
    while (k > 0) {
        result.pop_back();
        k--;
    }
    
    // Remove leading zeros
    int start = 0;
    while (start < result.size() && result[start] == '0') start++;
    
    string ans = result.substr(start);
    return ans.empty() ? "0" : ans;
}

// Task Scheduler (Greedy + Math)
// LeetCode: 621. Task Scheduler
// https://leetcode.com/problems/task-scheduler/
int leastInterval(vector<char>& tasks, int n) {
    vector<int> freq(26, 0);
    for (char task : tasks) freq[task - 'A']++;
    
    sort(freq.begin(), freq.end());
    int maxFreq = freq[25];
    int maxCount = 0;
    
    for (int f : freq) {
        if (f == maxFreq) maxCount++;
    }
    
    int result = (maxFreq - 1) * (n + 1) + maxCount;
    return max(result, (int)tasks.size());
}

// Huffman Coding (Greedy Tree Construction)
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;
    }
};

HuffmanNode* buildHuffmanTree(vector<pair<char,int>>& charFreq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
    for (auto& p : charFreq) {
        pq.push(new HuffmanNode(p.first, p.second));
    }
    
    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);
    }
    
    return pq.top();
}

// Assign Cookies
// LeetCode: 455. Assign Cookies
// https://leetcode.com/problems/assign-cookies/
int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    
    int i = 0, j = 0;
    while (i < g.size() && j < s.size()) {
        if (s[j] >= g[i]) i++;
        j++;
    }
    return i;
}

// Partition Labels
// LeetCode: 763. Partition Labels
// https://leetcode.com/problems/partition-labels/
vector<int> partitionLabels(string s) {
    vector<int> last(26, -1);
    for (int i = 0; i < s.size(); i++) {
        last[s[i] - 'a'] = i;
    }
    
    vector<int> result;
    int start = 0, end = 0;
    for (int i = 0; i < s.size(); i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}