Advanced Greedy Algorithms

Advanced greedy algorithms tackle complex optimization problems by making locally optimal choices. These techniques include interval scheduling, fractional knapsack, Huffman coding, and various graph algorithms that demonstrate the power of greedy strategies in competitive programming.

Interval Scheduling Problems

Interval scheduling is a classic greedy problem where we select the maximum number of non-overlapping intervals. The key insight is to sort by end times and greedily select intervals.

Interval Scheduling and Variants

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

struct Interval {
    int start, end;
    int weight; // for weighted version
    
    Interval(int s, int e, int w = 1) : start(s), end(e), weight(w) {}
};

class IntervalScheduling {
public:
    // Classic interval scheduling - maximum number of non-overlapping intervals
    static int maxIntervals(vector<Interval>& intervals) {
        if (intervals.empty()) return 0;
        
        // Sort by end time
        sort(intervals.begin(), intervals.end(), 
             [](const Interval& a, const Interval& b) {
                 return a.end < b.end;
             });
        
        int count = 1;
        int lastEnd = intervals[0].end;
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start >= lastEnd) {
                count++;
                lastEnd = intervals[i].end;
            }
        }
        
        return count;
    }
    
    // Weighted interval scheduling using greedy approximation
    static int maxWeightGreedy(vector<Interval>& intervals) {
        if (intervals.empty()) return 0;
        
        // Sort by weight/length ratio (greedy heuristic)
        sort(intervals.begin(), intervals.end(), 
             [](const Interval& a, const Interval& b) {
                 double ratioA = (double)a.weight / (a.end - a.start);
                 double ratioB = (double)b.weight / (b.end - b.start);
                 return ratioA > ratioB;
             });
        
        int totalWeight = 0;
        vector<bool> used(intervals.size(), false);
        
        for (int i = 0; i < intervals.size(); i++) {
            if (used[i]) continue;
            
            totalWeight += intervals[i].weight;
            used[i] = true;
            
            // Mark overlapping intervals as used
            for (int j = i + 1; j < intervals.size(); j++) {
                if (!used[j] && intervalsOverlap(intervals[i], intervals[j])) {
                    used[j] = true;
                }
            }
        }
        
        return totalWeight;
    }
    
    // Minimum intervals to cover a point
    static int minIntervalsToPoint(vector<Interval>& intervals, int point) {
        vector<Interval> covering;
        
        // Find intervals that cover the point
        for (const auto& interval : intervals) {
            if (interval.start <= point && point <= interval.end) {
                covering.push_back(interval);
            }
        }
        
        if (covering.empty()) return -1; // impossible
        
        // Sort by start time, then by end time
        sort(covering.begin(), covering.end(), 
             [](const Interval& a, const Interval& b) {
                 if (a.start != b.start) return a.start < b.start;
                 return a.end > b.end;
             });
        
        return 1; // At least one interval covers the point
    }
    
private:
    static bool intervalsOverlap(const Interval& a, const Interval& b) {
        return !(a.end <= b.start || b.end <= a.start);
    }
};

int main() {
    vector<Interval> intervals = {
        Interval(1, 3, 5), Interval(2, 5, 8), Interval(3, 6, 3),
        Interval(4, 7, 6), Interval(5, 8, 4), Interval(6, 9, 7)
    };
    
    cout << "Intervals (start, end, weight):" << endl;
    for (const auto& interval : intervals) {
        cout << "(" << interval.start << ", " << interval.end << ", " << interval.weight << ") ";
    }
    cout << endl;
    
    // Test classic interval scheduling
    vector<Interval> copy1 = intervals;
    int maxCount = IntervalScheduling::maxIntervals(copy1);
    cout << "\nMaximum non-overlapping intervals: " << maxCount << endl;
    
    // Test weighted interval scheduling
    vector<Interval> copy2 = intervals;
    int maxWeight = IntervalScheduling::maxWeightGreedy(copy2);
    cout << "Maximum weight (greedy approximation): " << maxWeight << endl;
    
    // Test point coverage
    int point = 4;
    vector<Interval> copy3 = intervals;
    int minCover = IntervalScheduling::minIntervalsToPoint(copy3, point);
    cout << "Point " << point << " can be covered by " << minCover << " interval(s)" << endl;
    
    return 0;
}

Interval scheduling problems demonstrate key greedy principles: sorting by the right criterion (end times for maximum intervals) and making locally optimal choices that lead to globally optimal solutions.

Fractional Knapsack Problem

Unlike the 0/1 knapsack problem, the fractional knapsack allows taking fractions of items. The greedy approach of sorting by value-to-weight ratio gives the optimal solution.

Fractional Knapsack Implementation

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

struct Item {
    int value, weight;
    double ratio;
    int index;
    
    Item(int v, int w, int idx) : value(v), weight(w), index(idx) {
        ratio = (double)value / weight;
    }
};

class FractionalKnapsack {
public:
    struct Solution {
        double maxValue;
        vector<double> fractions; // fraction of each item taken
        
        Solution(int n) : maxValue(0), fractions(n, 0) {}
    };
    
    static Solution solve(vector<Item>& items, int capacity) {
        int n = items.size();
        Solution solution(n);
        
        // Sort by value-to-weight ratio in descending order
        sort(items.begin(), items.end(), 
             [](const Item& a, const Item& b) {
                 return a.ratio > b.ratio;
             });
        
        int remainingCapacity = capacity;
        
        for (const auto& item : items) {
            if (remainingCapacity >= item.weight) {
                // Take the whole item
                solution.fractions[item.index] = 1.0;
                solution.maxValue += item.value;
                remainingCapacity -= item.weight;
            } else if (remainingCapacity > 0) {
                // Take fraction of the item
                double fraction = (double)remainingCapacity / item.weight;
                solution.fractions[item.index] = fraction;
                solution.maxValue += item.value * fraction;
                remainingCapacity = 0;
                break;
            }
        }
        
        return solution;
    }
    
    // Variant: Multiple knapsacks
    static vector<Solution> multipleKnapsacks(vector<Item>& items, vector<int>& capacities) {
        vector<Solution> solutions;
        
        // Sort items by ratio
        sort(items.begin(), items.end(), 
             [](const Item& a, const Item& b) {
                 return a.ratio > b.ratio;
             });
        
        for (int capacity : capacities) {
            vector<Item> availableItems = items; // copy for this knapsack
            Solution solution = solve(availableItems, capacity);
            solutions.push_back(solution);
        }
        
        return solutions;
    }
};

// Continuous knapsack with time constraints
class TimeConstrainedKnapsack {
public:
    struct Task {
        int value, time;
        double efficiency;
        int index;
        
        Task(int v, int t, int idx) : value(v), time(t), index(idx) {
            efficiency = (double)value / time;
        }
    };
    
    static double maxValueInTime(vector<Task>& tasks, int totalTime) {
        // Sort by efficiency (value per time unit)
        sort(tasks.begin(), tasks.end(), 
             [](const Task& a, const Task& b) {
                 return a.efficiency > b.efficiency;
             });
        
        double maxValue = 0;
        int remainingTime = totalTime;
        
        for (const auto& task : tasks) {
            if (remainingTime >= task.time) {
                maxValue += task.value;
                remainingTime -= task.time;
            } else if (remainingTime > 0) {
                // Partial task completion
                double fraction = (double)remainingTime / task.time;
                maxValue += task.value * fraction;
                break;
            }
        }
        
        return maxValue;
    }
};

int main() {
    // Test fractional knapsack
    vector<Item> items = {
        Item(60, 10, 0), Item(100, 20, 1), Item(120, 30, 2)
    };
    int capacity = 50;
    
    cout << "Items (value, weight, ratio):" << endl;
    for (const auto& item : items) {
        cout << "Item " << item.index << ": (" << item.value << ", " << item.weight 
             << ", " << fixed << setprecision(2) << item.ratio << ")" << endl;
    }
    
    FractionalKnapsack::Solution solution = FractionalKnapsack::solve(items, capacity);
    
    cout << "\nKnapsack capacity: " << capacity << endl;
    cout << "Maximum value: " << fixed << setprecision(2) << solution.maxValue << endl;
    cout << "Item fractions taken:" << endl;
    for (int i = 0; i < solution.fractions.size(); i++) {
        if (solution.fractions[i] > 0) {
            cout << "Item " << i << ": " << fixed << setprecision(2) 
                 << solution.fractions[i] * 100 << "%" << endl;
        }
    }
    
    // Test time-constrained tasks
    vector<TimeConstrainedKnapsack::Task> tasks = {
        TimeConstrainedKnapsack::Task(100, 20, 0),
        TimeConstrainedKnapsack::Task(60, 10, 1),
        TimeConstrainedKnapsack::Task(140, 40, 2)
    };
    int totalTime = 50;
    
    cout << "\nTasks (value, time, efficiency):" << endl;
    for (const auto& task : tasks) {
        cout << "Task " << task.index << ": (" << task.value << ", " << task.time 
             << ", " << fixed << setprecision(2) << task.efficiency << ")" << endl;
    }
    
    double maxTaskValue = TimeConstrainedKnapsack::maxValueInTime(tasks, totalTime);
    cout << "\nMaximum value in " << totalTime << " time units: " 
         << fixed << setprecision(2) << maxTaskValue << endl;
    
    return 0;
}

The fractional knapsack demonstrates the power of greedy algorithms when problems have the greedy choice property. Sorting by value-to-weight ratio ensures optimal substructure.

Key Takeaways

Advanced greedy algorithms require careful analysis of the greedy choice property and optimal substructure
Sorting by the right criterion is crucial - end times for intervals, ratios for knapsack problems
Greedy algorithms often provide optimal solutions for fractional problems and good approximations for discrete ones
Understanding when greedy works vs when dynamic programming is needed is essential for competitive programming