Greedy Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Most non-overlapping intervals: take the one that ends first, again and again.
// Touching ([1,3] then [3,5]) allowed here; use > instead of >= if the problem forbids it.
int maxNonOverlapping(vector<pair<int,int>> iv) {          // {start, end}
    sort(iv.begin(), iv.end(), [](auto& a, auto& b) { return a.second < b.second; });
    int count = 0;
    long long lastEnd = LLONG_MIN;
    for (auto& [s, e] : iv)
        if (s >= lastEnd) { count++; lastEnd = e; }         // fits after the last one taken
    return count;
}

// Partition into most parts: a part must reach the last occurrence of each of its letters.
vector<int> partitionByLast(const string& s) {
    int last[26] = {};
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
    vector<int> sizes;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) { sizes.push_back(end - start + 1); start = i + 1; }   // part closed
    }
    return sizes;
}

// The comparator IS the algorithm. Prove it with a swap: if a should come before b,
// swapping them in any answer must not make it better.

// Fractional knapsack: best value per weight first; compare ratios without division.
double fractional(vector<int> val, vector<int> wt, long long cap) {
    int n = val.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return 1LL * val[a] * wt[b] > 1LL * val[b] * wt[a];  // val[a]/wt[a] > val[b]/wt[b]
    });
    double total = 0;
    for (int i : idx) {
        if (cap == 0) break;
        long long take = min<long long>(cap, wt[i]);
        total += (double)val[i] * take / wt[i];
        cap -= take;
    }
    return total;
}

// Deadlines, one time unit each: by deadline, keep the best profits in a min-heap.
long long maxProfitJobs(vector<pair<int,int>> jobs) {         // {deadline, profit}
    sort(jobs.begin(), jobs.end());
    priority_queue<int, vector<int>, greater<int>> kept;
    for (auto& [d, p] : jobs) {
        kept.push(p);
        if ((int)kept.size() > d) kept.pop();                // too many jobs by time d: drop the cheapest
    }
    long long sum = 0;
    while (!kept.empty()) { sum += kept.top(); kept.pop(); }
    return sum;
}

// nums[i] = longest jump from i. Every index up to far is reachable.
bool canReachEnd(const vector<int>& nums) {
    int far = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > far) return false;                           // a gap nobody can jump over
        far = max(far, i + nums[i]);
    }
    return true;
}

// Fewest jumps: indexes reachable with k jumps form one block [.., curEnd] (a BFS level).
int minJumps(const vector<int>& nums) {
    int jumps = 0, curEnd = 0, far = 0;
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        far = max(far, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = far; }          // level finished: one more jump
    }
    return jumps;                                            // assumes the end is reachable
}

// Each need gets the smallest resource that satisfies it; count the matches.
int matchSmallestFit(vector<int> need, vector<int> res) {
    sort(need.begin(), need.end());
    sort(res.begin(), res.end());
    int i = 0, j = 0;
    while (i < (int)need.size() && j < (int)res.size()) {
        if (res[j] >= need[i]) i++;                          // match: this need is served
        j++;                                                 // too small now = too small for all later needs
    }
    return i;
}

// Beat b[] in as many positions as possible by permuting a[] (Tian Ji):
// strongest opponent first; win with our strongest, or sacrifice our weakest.
vector<int> advantage(vector<int> a, const vector<int>& b) {
    int n = a.size();
    sort(a.begin(), a.end());
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) { return b[x] > b[y]; });
    vector<int> res(n);
    int lo = 0, hi = n - 1;
    for (int k : order) res[k] = a[hi] > b[k] ? a[hi--] : a[lo++];
    return res;
}

// Circular route: net[i] = gain at i minus cost to go on. Return a start index or -1.
int startOfCircuit(const vector<int>& net) {
    long long total = 0, tank = 0;
    int start = 0;
    for (int i = 0; i < (int)net.size(); i++) {
        total += net[i];
        tank += net[i];
        if (tank < 0) { start = i + 1; tank = 0; }           // no start in start..i can pass i
    }
    return total < 0 ? -1 : start;
}

// Rules on both neighbours: one pass for each side, then take the max.
long long twoPassMin(const vector<int>& r) {                 // Candy
    int n = r.size();
    vector<int> c(n, 1);
    for (int i = 1; i < n; i++) if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--) if (r[i] > r[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
    return accumulate(c.begin(), c.end(), 0LL);
}

// Repeatedly merge the two smallest (Huffman cost, connecting ropes).
long long mergeTwoSmallest(const vector<int>& w) {
    priority_queue<long long, vector<long long>, greater<long long>> pq(w.begin(), w.end());
    long long cost = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        cost += a + b;
        pq.push(a + b);                                      // the merged node may be the next smallest
    }
    return cost;
}

// Most frequent first, never the same as the last one (no two equal neighbours).
string noTwoAdjacent(const string& s) {
    int cnt[26] = {};
    for (char ch : s) cnt[ch - 'a']++;
    priority_queue<pair<int,char>> pq;                       // {count, letter}, biggest count on top
    for (int c = 0; c < 26; c++) if (cnt[c]) pq.push({cnt[c], char('a' + c)});
    string out;
    while (pq.size() >= 2) {
        auto [c1, x] = pq.top(); pq.pop();
        auto [c2, y] = pq.top(); pq.pop();
        out += x; out += y;                                  // two different letters per round
        if (--c1) pq.push({c1, x});
        if (--c2) pq.push({c2, y});
    }
    if (!pq.empty()) {
        if (pq.top().first > 1) return "";                   // one letter left over more than once
        out += pq.top().second;
    }
    return out;
}