Greedy Algorithms

// Activity Selection — O(n log n)
// Sort by end time; greedily pick earliest-finishing non-conflicting interval
int maxNonOverlapping(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b){ return a[1] < b[1]; }); // sort by end time
    int count = 1, lastEnd = intervals[0][1];
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] >= lastEnd) {
            count++; lastEnd = intervals[i][1];
        }
    }
    return count;
}

// Merge Overlapping Intervals — O(n log n)
// Sort by start time; merge when current interval overlaps previous
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end()); // sort by start
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (res.empty() || iv[0] > res.back()[1]) res.push_back(iv);
        else res.back()[1] = max(res.back()[1], iv[1]);
    }
    return res;
}

// JUMP GAME I (LC 55) — Can you reach the last index?
bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > maxReach) return false;    // stuck
        maxReach = max(maxReach, i + nums[i]);
    }
    return true;
}

// JUMP GAME II (LC 45) — Minimum jumps to reach end
int jump(vector<int>& nums) {
    int jumps = 0, currEnd = 0, farthest = 0;
    for (int i = 0; i < (int)nums.size()-1; i++) {
        farthest = max(farthest, i + nums[i]);
        if (i == currEnd) {   // reached end of jump range
            jumps++; currEnd = farthest;
        }
    }
    return jumps;
}

// Kadane's Algorithm — O(n) O(1)
// LeetCode 53 — Maximum Subarray
int maxSubArray(vector<int>& nums) {
    int currSum = nums[0], maxSum = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        currSum = max(nums[i], currSum + nums[i]);
        maxSum = max(maxSum, currSum);
    }
    return maxSum;
}

// LeetCode 134 — Gas Station
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalSurplus = 0, currSurplus = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int diff = gas[i] - cost[i];
        totalSurplus += diff; currSurplus += diff;
        if (currSurplus < 0) { // Reset if deficit
            start = i + 1; currSurplus = 0;
        }
    }
    return totalSurplus >= 0 ? start : -1;
}

// Huffman Encoding — O(n log n)
struct HNode {
    int freq; char ch;
    HNode *left, *right;
    HNode(int f, char c) : freq(f), ch(c), left(nullptr), right(nullptr) {}
};

HNode* buildHuffman(unordered_map<char,int>& freq) {
    auto cmp = [](HNode* a, HNode* b){ return a->freq > b->freq; };
    priority_queue<HNode*, vector<HNode*>, decltype(cmp)> pq(cmp);

    for (auto& [ch, f] : freq) pq.push(new HNode(f, ch));

    while (pq.size() > 1) {
        HNode* l = pq.top(); pq.pop();
        HNode* r = pq.top(); pq.pop();
        HNode* parent = new HNode(l->freq + r->freq, '\0');
        parent->left = l; parent->right = r;
        pq.push(parent);
    }
    return pq.top(); // root
}

// Minimum intervals to remove so remaining are non-overlapping
// Time: O(n log n)  Space: O(1)
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b){ return a[1] < b[1]; });
    int keep = 1, lastEnd = intervals[0][1];
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] >= lastEnd) {
            keep++; lastEnd = intervals[i][1];
        }
    }
    return (int)intervals.size() - keep;
}

// Partition Labels — O(n)
// Partition string so each letter appears in at most one part.
vector<int> partitionLabels(string s) {
    int last[26] = {};
    for (int i = 0; i < (int)s.size(); i++) last[s[i]-'a'] = i;

    vector<int> result;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i]-'a']); // extend partition
        if (i == end) {                 // partition boundary found
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            if (i > maxReach) {
                return false; // stranded at i
            }
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= n - 1) {
                return true;  // early exit
            }
        }
        return true;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        
        // 1. Sort by start coordinate
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> merged;
        merged.push_back(intervals[0]);
        
        // 2. Scan and merge
        for (int i = 1; i < intervals.size(); i++) {
            int currentStart = intervals[i][0];
            int currentEnd = intervals[i][1];
            int lastEnd = merged.back()[1];
            
            if (currentStart <= lastEnd) {
                // Overlap: update ending
                merged.back()[1] = max(lastEnd, currentEnd);
            } else {
                // No overlap: strictly later interval
                merged.push_back(intervals[i]);
            }
        }
        
        return merged;
    }
};