More Greedy Problems

Real-world analogy

What is it?

This lesson expands your greedy algorithm toolkit with more classic problems. We explore the fractional knapsack (take the most valuable items per unit weight), the minimum platforms problem (handle overlapping intervals), and develop a systematic approach to recognize when greedy algorithms are applicable and how to prove they work.

Real-world relevance

Fractional knapsack is used in investment portfolio optimization (allocate budget to highest-return assets), in cargo loading (fill a truck with the most valuable goods), and in bandwidth allocation (give more bandwidth to higher-priority traffic). The minimum platforms problem is literally used by train stations and airports to plan infrastructure!

Key points

• Fractional Knapsack Problem — You have a bag that holds W kg. Items have weights and values. Unlike 0/1 knapsack, you can take FRACTIONS of items. Greedy works perfectly here: sort by value/weight ratio descending, take as much as possible of each item starting from the best ratio.
• Why Greedy Works for Fractional Knapsack — Since we can take fractions, there is no reason not to take the highest-value-per-kg item first. Each unit of weight we use on the best ratio item gives us more value than using it on anything else. This greedy choice is always optimal.
• Fractional Knapsack Example — Bag holds 50 kg. Items: (60 value, 10 kg), (100 value, 20 kg), (120 value, 30 kg). Ratios: 6, 5, 4. Take all of item 1 (10kg, value 60), all of item 2 (20kg, value 100), then 20/30 of item 3 (20kg, value 80). Total: 50kg, value 240.
• Minimum Platforms Problem — Trains arrive and depart at different times. Find the minimum number of platforms needed so no train waits. Greedy approach: sort all arrival and departure times. Scan through — arrival means +1 platform needed, departure means -1. Track the maximum at any point.
• How Minimum Platforms Works — Arrivals: [9:00, 9:40, 9:50, 11:00]. Departures: [9:10, 12:00, 11:20, 11:30]. Sort all events by time. Walk through and count: +1 at arrival, -1 at departure. The peak count is the answer. It is like watching a parking lot and counting the maximum cars at any moment.
• Approaching Greedy Problems — Step 1: Think about what to sort by. Step 2: Determine the greedy rule (what is the 'best' choice at each step?). Step 3: Walk through examples to verify. Step 4: Try to find a counterexample where greedy fails. If you cannot find one, it probably works!
• Proving Greedy Correctness — The exchange argument: assume an optimal solution differs from greedy at some step. Show that swapping to match the greedy choice does not make things worse. If every swap is safe, greedy gives an optimal solution. This is the formal way to verify your greedy approach.
• Common Greedy Problem Types — Classic greedy problems include: activity selection, fractional knapsack, coin change (standard denominations), job scheduling with deadlines, minimum spanning tree (Kruskal/Prim), and Huffman coding. Recognizing these patterns is key to solving new problems.
• Greedy vs Dynamic Programming — If greedy fails (like coin change with weird denominations), you often need dynamic programming (DP) — which we will learn later. DP considers ALL choices and picks the best, while greedy only considers the current best. Greedy is faster but less general.

Code example

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Fractional Knapsack
    int n, W;
    cin >> n >> W;
    vector<pair<double, pair<int,int>>> items(n); // {ratio, {value, weight}}

    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        double ratio = (double)v / w;
        items[i] = {ratio, {v, w}};
    }

    // Sort by value/weight ratio in descending order
    sort(items.begin(), items.end(), greater<pair<double, pair<int,int>>>());

    double totalValue = 0;
    int remainingCapacity = W;

    for (int i = 0; i < n && remainingCapacity > 0; i++) {
        int w = items[i].second.second;
        int v = items[i].second.first;

        if (w <= remainingCapacity) {
            // Take the whole item
            totalValue += v;
            remainingCapacity -= w;
            cout << "Take all of item (value=" << v << ", weight=" << w << ")\n";
        } else {
            // Take a fraction
            double fraction = (double)remainingCapacity / w;
            totalValue += v * fraction;
            cout << "Take " << fixed << setprecision(2) << fraction * 100
                 << "% of item (value=" << v << ", weight=" << w << ")\n";
            remainingCapacity = 0;
        }
    }

    cout << "Total value: " << fixed << setprecision(2) << totalValue << "\n\n";

    // Minimum Platforms
    int trains;
    cin >> trains;
    vector<int> arrivals(trains), departures(trains);
    for (int i = 0; i < trains; i++) cin >> arrivals[i];
    for (int i = 0; i < trains; i++) cin >> departures[i];

    sort(arrivals.begin(), arrivals.end());
    sort(departures.begin(), departures.end());

    int platforms = 0, maxPlatforms = 0;
    int i = 0, j = 0;
    while (i < trains) {
        if (arrivals[i] <= departures[j]) {
            platforms++;
            maxPlatforms = max(maxPlatforms, platforms);
            i++;
        } else {
            platforms--;
            j++;
        }
    }
    cout << "Minimum platforms needed: " << maxPlatforms << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. double ratio = (double)v / w; — we calculate the value-per-unit-weight ratio for each item. The (double) cast ensures we get decimal division, not integer division.
2. 2. sort(items.begin(), items.end(), greater()); — we sort items by ratio in descending order. greater<> reverses the default ascending sort. Now the best value-per-weight items come first.
3. 3. if (w <= remainingCapacity) — if the item fits entirely in our remaining capacity, take the whole thing. Add its full value and reduce capacity by its weight.
4. 4. double fraction = (double)remainingCapacity / w; — if the item does not fit entirely, we take a fraction. If we have 20 kg left and the item weighs 30 kg, we take 20/30 = 2/3 of it.
5. 5. totalValue += v * fraction; — we add the proportional value. If we take 2/3 of an item worth 120, we get 80 value.
6. 6. sort(arrivals...) and sort(departures...) — for minimum platforms, we sort arrivals and departures separately. Then we process events in time order using two pointers.
7. 7. if (arrivals[i] <= departures[j]) — if the next event is an arrival (happens before or at the same time as the next departure), we need one more platform. Otherwise, a train left and we free a platform.

Spot the bug

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

int main() {
    int n = 3, W = 50;
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};

    // Sort by value (descending)
    // (simplified: just process in order)
    double totalValue = 0;
    int remaining = W;

    for (int i = 0; i < n; i++) {
        if (weights[i] <= remaining) {
            totalValue += values[i];
            remaining -= weights[i];
        }
    }

    cout << fixed << setprecision(2) << totalValue << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Fractional Knapsack (GeeksforGeeks)
• Greedy Algorithm Problems (YouTube)
• Stick Lengths (CSES)