Understanding Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step with the hope of finding a global optimum. It does not guarantee a globally optimal solution for all problems, but it works well when the problem exhibits optimal substructure and the greedy choice property.

When Greedy Works—and When It Doesn’t

Applicable example: Selecting 3 bills from {100, 100, 50, 20, 20, 10} to maximize total value. Always picking the largest available bill yields the optimal sum (220).

Non-applicable example: The 0/1 knapsack problem with items (weight, value): (6,9), (5,7), (3,3) and capacity 8. Greedy by value/weight fails; dynamic programming is required.

Classic Problems Solved with Greedy Strategies

1. Removing Digits for Minimum Number

Problem: Given a string of digits (length ≤ 240) and an integer s, remove s digits to form the smallest possible number (no leading zeros).

Strategy: Repeatedly remove the first digit that is greater than its next neighbor (i.e., the leftmost peak in the sequence).

#include <iostream>
#include <string>
using namespace std;

int main() {
    string num;
    int s;
    cin >> num >> s;
    
    while (s-- > 0) {
        size_t i = 0;
        while (i + 1 < num.size() && num[i] <= num[i + 1]) ++i;
        num.erase(i, 1);
    }
    
    // Remove leading zeros
    size_t start = num.find_first_not_of('0');
    if (start == string::npos) cout << "0";
    else cout << num.substr(start);
    return 0;
}

2. Minimum Boats for People

Problem: Each boat holds ≤2 people and has weight limit w. Minimize boats needed.

Strategy: Sort weights. Pair lightest with heaviest if possible; otherwise, heaviest goes alone.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int w, n;
    cin >> w >> n;
    int weights[30000];
    for (int i = 0; i < n; ++i) cin >> weights[i];
    sort(weights, weights + n);
    
    int left = 0, right = n - 1, boats = 0;
    while (left <= right) {
        if (left == right || weights[left] + weights[right] <= w) ++left;
        --right;
        ++boats;
    }
    cout << boats;
    return 0;
}

3. Maximum Submatrix Sum

Problem: Find the contiguous submatrix with the largest sum in an N×N matrix.

Strategy: Compress rows into 1D arrays using prefix sums, then apply Kadane’s algorithm on each compressed array.

#include <iostream>
#include <climits>
using namespace std;

const int MAX = 100;
int mat[MAX][MAX];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            cin >> mat[i][j];
            if (i > 0) mat[i][j] += mat[i-1][j];
        }

    int best = INT_MIN;
    for (int top = 0; top < n; ++top) {
        for (int bottom = top; bottom < n; ++bottom) {
            int current = 0;
            for (int col = 0; col < n; ++col) {
                int val = mat[bottom][col] - (top > 0 ? mat[top-1][col] : 0);
                current = max(val, current + val);
                best = max(best, current);
            }
        }
    }
    cout << best;
    return 0;
}

4. Minimum Operations to Transform a to b

Problem: Allowed operations: increment by 1 or multiply by k. Find min steps from a to b.

Strategy: Work backwards from b to a. If divisible by k and quotient ≥ a, divide; else subtract remainder.

#include <iostream>
using namespace std;

int main() {
    long long a, b, k;
    cin >> a >> b >> k;
    
    if (k == 0) {
        cout << (b == 0 ? 1 : b - a);
        return 0;
    }
    if (k == 1) {
        cout << b - a;
        return 0;
    }
    
    long long steps = 0;
    while (b > a) {
        if (b % k == 0 && b / k >= a) {
            steps += 1;
            b /= k;
        } else {
            long long r = b % k;
            steps += r;
            b -= r;
            if (b < a) steps += (a - b);
        }
    }
    cout << steps;
    return 0;
}

5. Radar Installation

Problem: Place minimum radars on x-axis (radius d) to cover all islands at (x,y).

Strategy: For each island, compute interval on x-axis where radar can cover it. Sort intervals by right endpoint; place radar at rightmost point of earliest-ending uncovered interval.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

struct Interval { double left, right; };

bool cmp(const Interval& a, const Interval& b) {
    return a.right < b.right;
}

int main() {
    int n; double d;
    cin >> n >> d;
    vector<Interval> intervals;
    
    for (int i = 0; i < n; ++i) {
        double x, y;
        cin >> x >> y;
        if (y > d) { cout << -1; return 0; }
        double dx = sqrt(d*d - y*y);
        intervals.push_back({x - dx, x + dx});
    }
    
    sort(intervals.begin(), intervals.end(), cmp);
    double last_radar = -1e9;
    int count = 0;
    
    for (auto& iv : intervals) {
        if (last_radar < iv.left) {
            ++count;
            last_radar = iv.right;
        }
    }
    cout << count;
    return 0;
}

6. Minimum Milking Machines

Problem: Assign milking intervals to machines so no overlap per machine; minimize machines used.

Strategy: Sort cows by start time. Use a min-heap (priority queue) to track end times of active machines. Assign to earliest-ending available machine; if none, add new machine.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Cow { int start, end, id; };

int main() {
    int c;
    cin >> c;
    vector<Cow> cows(c);
    for (int i = 0; i < c; ++i) {
        cin >> cows[i].start >> cows[i].end;
        cows[i].id = i;
    }
    sort(cows.begin(), cows.end(), [](const Cow& a, const Cow& b) {
        return a.start < b.start;
    });
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // {end_time, machine_id}
    vector<int> assignment(c);
    int machine_count = 0;
    
    for (auto& cow : cows) {
        if (!pq.empty() && pq.top().first <= cow.start) {
            auto [_, id] = pq.top(); pq.pop();
            assignment[cow.id] = id;
            pq.push({cow.end, id});
        } else {
            assignment[cow.id] = ++machine_count;
            pq.push({cow.end, machine_count});
        }
    }
    
    cout << machine_count << "\n";
    for (int id : assignment) cout << id << "\n";
    return 0;
}

7. Sunscreen Assignment

Problem: Assign sunscreen bottles (fixed SPF, limited quantity) to cows (SPF range) to maximize covered cows.

Strategy: Sort cows by upper SPF limit. For each cow, assign the smallest SPF sunscreen that fits its range and is still available.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int C, L;
    cin >> C >> L;
    vector<pair<int, int>> cows(C);
    for (auto& c : cows) cin >> c.first >> c.second;
    
    vector<pair<int, int>> lotions(L);
    for (auto& l : lotions) cin >> l.first >> l.second;
    
    sort(cows.begin(), cows.end(), [](auto& a, auto& b) {
        return a.second < b.second;
    });
    sort(lotions.begin(), lotions.end());
    
    int covered = 0;
    for (auto& cow : cows) {
        for (auto& lotion : lotions) {
            if (lotion.second > 0 && lotion.first >= cow.first && lotion.first <= cow.second) {
                --lotion.second;
                ++covered;
                break;
            }
        }
    }
    cout << covered;
    return 0;
}

8. Task Assignment for Maximum Profit

Problem: Assign tasks (time, difficulty) to machines (max time, max difficulty) to maximize profit = 500×time + 2×difficulty.

Strategy: Sort tasks and machines by time descending. For each task, among eligible machines (time ≥ task.time), pick the one with smallest difficulty ≥ task.difficulty.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    
    vector<pair<int, int>> machines(N), tasks(M);
    for (auto& m : machines) cin >> m.first >> m.second;
    for (auto& t : tasks) cin >> t.first >> t.second;
    
    sort(machines.rbegin(), machines.rend());
    sort(tasks.rbegin(), tasks.rend());
    
    vector<int> count(101, 0); // count[difficulty] = available machines
    long long profit = 0, assigned = 0;
    int j = 0;
    
    for (int i = 0; i < M; ++i) {
        while (j < N && machines[j].first >= tasks[i].first) {
            ++count[machines[j].second];
            ++j;
        }
        for (int d = tasks[i].second; d <= 100; ++d) {
            if (count[d] > 0) {
                --count[d];
                ++assigned;
                profit += 500LL * tasks[i].first + 2 * tasks[i].second;
                break;
            }
        }
    }
    cout << assigned << " " << profit;
    return 0;
}

9. Tree Coloring with Minimum Cost

Problem: Color tree nodes (root first, then children). Cost = (coloring time) × (node cost). Minimize total cost.

Strategy: Use a greedy merge: always color the node with highest cost-per-unit-time ratio next. Implemented via union-find-like merging of subtrees.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, root;
    cin >> n >> root;
    vector<long long> cost(n+1), size(n+1, 1);
    vector<int> parent(n+1);
    vector<bool> visited(n+1, false);
    
    for (int i = 1; i <= n; ++i) {
        cin >> cost[i];
        parent[i] = i;
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        parent[v] = u;
    }
    
    long long total = 0;
    for (int i = 1; i <= n; ++i) total += cost[i];
    
    for (int step = 1; step < n; ++step) {
        int best = -1;
        for (int i = 1; i <= n; ++i) {
            if (i == root || visited[i]) continue;
            if (best == -1 || cost[i] * size[best] > cost[best] * size[i])
                best = i;
        }
        
        int p = parent[best];
        while (visited[p]) p = parent[p];
        
        total += cost[best] * size[p];
        cost[p] += cost[best];
        size[p] += size[best];
        visited[best] = true;
    }
    cout << total;
    return 0;
}