Greedy Algorithms are algorithmic techniques that choose the optimal choice at each step with the hope of achieving a globally optimal solution. Although not always correct, they often provide good and efficient results.
- Optimization problems - Find optimal values (min/max)
- Scheduling problems - Job scheduling, meeting rooms
- Selection problems - Choose elements satisfying conditions
- Partition problems - Divide arrays/strings into parts
- Interval problems - Sort and select intervals
// Choose maximum number of activities from n activities
int activitySelection(vector<pair<int, int>>& activities) {
if (activities.empty()) return 0;
// Sort by end time
sort(activities.begin(), activities.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
});
int count = 1; // Choose first activity
int lastEnd = activities[0].second;
for (int i = 1; i < activities.size(); i++) {
if (activities[i].first >= lastEnd) {
count++;
lastEnd = activities[i].second;
}
}
return count;
}Time Complexity: O(n log n)
Space Complexity: O(1)
// Knapsack with divisible items
double fractionalKnapsack(vector<pair<int, int>>& items, int capacity) {
// Sort by value/weight ratio in descending order
sort(items.begin(), items.end(),
[](const auto& a, const auto& b) {
return (double)a.second / a.first > (double)b.second / b.first;
});
double totalValue = 0.0;
int remainingCapacity = capacity;
for (const auto& [weight, value] : items) {
if (remainingCapacity >= weight) {
// Take entire item
totalValue += value;
remainingCapacity -= weight;
} else {
// Take partial item
totalValue += (double)value * remainingCapacity / weight;
break;
}
}
return totalValue;
}Time Complexity: O(n log n)
Space Complexity: O(1)
// Build Huffman tree for data compression
struct HuffmanNode {
char data;
int frequency;
HuffmanNode *left, *right;
HuffmanNode(char d, int freq) : data(d), frequency(freq), left(nullptr), right(nullptr) {}
};
struct CompareNodes {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->frequency > b->frequency;
}
};
HuffmanNode* buildHuffmanTree(vector<pair<char, int>>& frequencies) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> pq;
// Create leaf nodes
for (const auto& [ch, freq] : frequencies) {
pq.push(new HuffmanNode(ch, freq));
}
// Build tree
while (pq.size() > 1) {
HuffmanNode* left = pq.top(); pq.pop();
HuffmanNode* right = pq.top(); pq.pop();
HuffmanNode* parent = new HuffmanNode('\0', left->frequency + right->frequency);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}// Sort intervals for optimization
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// Sort by start time
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= merged.back()[1]) {
// Merge intervals
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
// Add new interval
merged.push_back(intervals[i]);
}
}
return merged;
}
// Find the minimum number of meeting rooms needed
int minMeetingRooms(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
vector<int> starts, ends;
for (const auto& interval : intervals) {
starts.push_back(interval[0]);
ends.push_back(interval[1]);
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, endPtr = 0;
for (int start : starts) {
if (start < ends[endPtr]) {
rooms++; // Need new room
} else {
endPtr++; // Can reuse old room
}
}
return rooms;
}// Find the starting point to complete a circuit
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalGas = 0, currentGas = 0, start = 0;
for (int i = 0; i < gas.size(); i++) {
totalGas += gas[i] - cost[i];
currentGas += gas[i] - cost[i];
if (currentGas < 0) {
start = i + 1;
currentGas = 0;
}
}
return totalGas >= 0 ? start : -1;
}// Check if you can jump to the end of the array
bool canJump(vector<int>& nums) {
int maxReach = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > maxReach) return false; // Cannot reach position i
maxReach = max(maxReach, i + nums[i]);
if (maxReach >= nums.size() - 1) return true;
}
return true;
}
// Find the minimum number of jumps
int jump(vector<int>& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.size() - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}// Choose the optimal choice at each step
// Example: Choose the interval that finishes first
sort(intervals.begin(), intervals.end(),
[](const auto& a, const auto& b) {
return a.second < b.second; // Sort by end time
});// The optimal solution contains the optimal solution of the subproblem
// Example: If item i is chosen, then we need to solve the problem with capacity - weight[i]// Prove that the solution cannot be improved by exchanging
// Often used to prove correctness// Modern C++23 approach with ranges
auto activitySelectionModern = [&](const auto& activities) -> int {
if (activities.empty()) return 0;
// Use std::ranges::sort
auto sorted = activities | std::views::all;
std::ranges::sort(sorted, {}, &std::pair<int, int>::second);
int count = 1;
int lastEnd = activities[0].second;
// Use std::views::drop to skip the first element
for (const auto& [start, end] : activities | std::views::drop(1)) {
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
return count;
};// Calculate greedy with std::accumulate
auto calculateGreedyValue = [&](const auto& items, int capacity) -> double {
// Sort by value/weight ratio
auto sorted = items | std::views::all;
std::ranges::sort(sorted, std::greater{},
[](const auto& item) { return (double)item.second / item.first; });
// Use std::accumulate to calculate the sum
return std::accumulate(sorted.begin(), sorted.end(), 0.0,
[capacity](double acc, const auto& item) mutable {
if (capacity <= 0) return acc;
int take = std::min(capacity, item.first);
capacity -= take;
return acc + (double)item.second * take / item.first;
});
};| Pattern | Time | Space | Best For |
|---|---|---|---|
| Activity Selection | O(n log n) | O(1) | Scheduling problems |
| Fractional Knapsack | O(n log n) | O(1) | Resource allocation |
| Interval Merging | O(n log n) | O(n) | Time-based problems |
| Jump Game | O(n) | O(1) | Array traversal |
- Dynamic Programming - When greedy is not correct
- Two Pointers - Combined with greedy
- Sorting - Often necessary for greedy
- Heap/Priority Queue - Choose the optimal
// Terminate early when possible
if (maxReach >= target) return true;
if (currentSum >= target) break;// Use simple variables instead of complex structures
int maxReach = 0; // Instead of vector<bool> visited// Use heuristics to guide selection
// Example: Choose item with the highest value/weight ratioRemember: Greedy Algorithms need to prove correctness. Practice to identify patterns! 🚀