Greedy Algorithms
The pattern: At each step, make the locally optimal choice — the best option right now — and trust that this leads to the globally optimal solution. No backtracking, no future lookahead. Greedy works when the “best local choice” provably leads to the best overall answer.
Why this matters in interviews: Greedy problems are fast to code (usually O(n log n) due to sorting) and elegant, but the hard part is proving the greedy choice is correct. Interviewers want to see you articulate WHY greedy works, not just the code.
When to Recognize It
- The problem asks for minimum/maximum something and the solution can be built incrementally
- Sorting the input by some criterion reveals an obvious strategy
- You can argue: “taking the best available option now never hurts the future”
- Keywords: “minimum number of intervals,” “maximum activities,” “jump to the end,” “assign tasks”
- Interval problems: sort by end time. Jump problems: track the farthest reachable position.
How It Works
Think of it like filling a backpack at a buffet with limited plate space. The greedy strategy: always grab the dish with the best value-to-size ratio first. You don’t reconsider — you just keep grabbing the best remaining option until you’re full.
flowchart LR
A["Sort input by criterion"]:::client
B["Pick best available option"]:::service
C["Update state"]:::data
D["Repeat until done"]:::service
A --> B
B --> C
C --> D
D --> B
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
The key question: “Does choosing the locally best option ever prevent us from finding the globally best solution?” If the answer is no, greedy works.
Template Code
Code
# Jump Game: can you reach the last index?
def can_jump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False # can't reach this position
farthest = max(farthest, i + nums[i])
return True
# Jump Game II: minimum jumps to reach end
def min_jumps(nums):
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end: # must jump now
jumps += 1
current_end = farthest
return jumps
# Merge Intervals
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged// Jump Game
boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// Jump Game II
int minJumps(int[] nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
// Merge Intervals
int[][] mergeIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.add(intervals[i]);
}
}
return merged.toArray(new int[0][]);
}// Jump Game
bool canJump(vector<int>& nums) {
int farthest = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > farthest) return false;
farthest = max(farthest, i + nums[i]);
}
return true;
}
// Jump Game II
int minJumps(vector<int>& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < (int)nums.size() - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
// Merge Intervals
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged = {intervals[0]};
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= merged.back()[1]) {
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
merged.push_back(intervals[i]);
}
}
return merged;
}// Jump Game
function canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// Jump Game II
function minJumps(nums) {
let jumps = 0, currentEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
// Merge Intervals
function mergeIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.push(intervals[i]);
}
}
return merged;
}Variations
Non-Overlapping Intervals (Interval Scheduling)
Sort by end time. Greedily pick the interval that finishes earliest (leaves the most room for future intervals). Count how many you need to remove.
Code
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by END time
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # keep this interval
else:
count += 1 # remove this interval (overlaps)
return countint eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0, prevEnd = Integer.MIN_VALUE;
for (int[] interval : intervals) {
if (interval[0] >= prevEnd) prevEnd = interval[1];
else count++;
}
return count;
}int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](auto& a, auto& b) { return a[1] < b[1]; });
int count = 0, prevEnd = INT_MIN;
for (auto& iv : intervals) {
if (iv[0] >= prevEnd) prevEnd = iv[1];
else count++;
}
return count;
}function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]);
let count = 0, prevEnd = -Infinity;
for (const [start, end] of intervals) {
if (start >= prevEnd) prevEnd = end;
else count++;
}
return count;
}Task Scheduler (Cooldown Constraint)
The most frequent task dictates the minimum time. Fill idle slots with other tasks. Greedy insight: schedule the most frequent task first to minimize idle gaps.
Activity Selection
Classic greedy: sort activities by finish time, always pick the one that ends earliest and doesn’t conflict with the last picked.
Complexity
| Problem | Time | Space |
|---|---|---|
| Jump Game | O(n) | O(1) |
| Jump Game II | O(n) | O(1) |
| Merge Intervals | O(n log n) | O(n) |
| Non-Overlapping Intervals | O(n log n) | O(1) |
| Task Scheduler | O(n) | O(1) |
Most greedy solutions are O(n) after O(n log n) sorting.
Common Mistakes
- Sorting by the wrong criterion — for interval scheduling, sort by END time (not start time). Sorting by start time maximizes overlap, not selection.
- Not proving greedy correctness — just because greedy gives the right answer on examples doesn’t mean it’s correct. Think about exchange arguments: “if we swap a greedy choice with a non-greedy one, does the answer get worse?”
- Applying greedy when DP is needed — greedy fails for 0/1 knapsack, coin change (with arbitrary denominations), and problems where local optimality doesn’t guarantee global optimality
- Off-by-one in Jump Game II — iterate to
n-2(notn-1) because you don’t need to jump FROM the last index
Practice Problems
Key Takeaways
- Greedy = make the best local choice at each step, with no backtracking
- The hardest part isn’t coding — it’s proving WHY greedy works. Practice the “exchange argument.”
- Interval problems: sort by end time. Jump problems: track farthest reachable position.
- If greedy doesn’t obviously work, it probably doesn’t. Fall back to DP.