These are the notes for DSA episode 59, the start of the greedy chapter. A greedy algorithm makes the choice that looks best right now and never undoes it. That's sometimes brilliant and sometimes wrong, so every greedy rule needs a proof. Part 1: one banquet hall, many bookings; host the most events (activity selection, the idea behind LeetCode 435). Trying every subset is correct but Time Limit Exceeded on just 30 bookings; two tempting greedy rules (shortest first, earliest start first) give 1 where 2 is possible; earliest finish first is right, proved by the exchange argument. Part 2: stepping stones across a stream: Jump Game (can you reach the end?) and Jump Game II (fewest jumps). Recursion over every jump times out on 42 stones; keeping only the farthest reachable stone solves both in one pass. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.
The problem, in real life
A banquet hall owner has one hall and a day's booking requests: weddings, birthdays, office meetings. Each request has a start and an end time. Two events can't use the hall at once, but one may start the moment another ends. Every event pays the same fee. Which requests should the owner accept to host the most events?
| In the hall | In code |
|---|---|
| A booking request | an interval [start, end) |
| Two bookings clash | a.start < b.end && b.start < a.end |
| One ends as the next starts | touching: allowed (b.start >= a.end) |
| The most events | the largest set of non-overlapping intervals |
Every word, from zero
- Interval
[start, end): fromstartup to (not including)end. - Overlap: two intervals overlap when each starts before the other ends:
a.start < b.end && b.start < a.end. - Touching:
[1, 2)and[2, 3)don't overlap. - Subset: any selection of the requests (2ⁿ of them for n requests).
- Bitmask: an integer whose bit
isays whether requestiis chosen. - Greedy algorithm: at each step take the best-looking choice by some rule, and never undo it.
- Counterexample: a small input on which a rule gives the wrong answer; one is enough to kill a rule.
- Exchange argument: a proof that a greedy choice is safe: take any optimal answer, swap in the greedy choice, and show it's still optimal.
- Reach /
far: the farthest index you can get to so far. - BFS level: all positions reachable with the same number of jumps.
Part 1: activity selection
Problem
Given n events [start, end), return the most events one hall can host with no overlap.
| events | Answer |
|---|---|
[1,4] [3,5] [0,6] [5,7] [3,9] [5,9] [6,10] [8,11] [8,12] [2,14] [12,16] |
4 ([1,4] [5,7] [8,11] [12,16]) |
[1,5] [4,7] [6,10] |
2 |
[1,2] [2,3] |
2 (touching is fine) |
LeetCode 435, Non-overlapping Intervals, asks for the fewest intervals to remove so the rest don't overlap: that is n - maxEvents (it also treats touching intervals as non-overlapping).
Obvious idea: try every subset
import java.util.*;
public class Main {
static int maxEvents(int[][] ev) {
int n = ev.length, best = 0;
for (int mask = 0; mask < (1 << n); mask++)
if (fits(ev, mask)) best = Math.max(best, Integer.bitCount(mask));
return best;
}
static boolean fits(int[][] ev, int mask) {
for (int i = 0; i < ev.length; i++)
for (int j = i + 1; j < ev.length; j++)
if ((mask >> i & 1) == 1 && (mask >> j & 1) == 1
&& ev[i][0] < ev[j][1] && ev[j][0] < ev[i][1]) return false;
return true;
}
public static void main(String[] args) {
int[][] hall = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9},
{6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};
System.out.println(maxEvents(hall));
}
}
4
Correct. With 30 random bookings: Time Limit Exceeded: 2^30 ≈ 107 crore subsets, each checking up to 30 · 29 / 2 pairs.
Two greedy traps
Sort by some rule, take each event that still fits:
import java.util.*;
public class Main {
static int greedy(int[][] ev, Comparator<int[]> order) {
int[][] e = ev.clone();
Arrays.sort(e, order);
List<int[]> taken = new ArrayList<>();
for (int[] x : e) {
boolean ok = true;
for (int[] t : taken)
if (x[0] < t[1] && t[0] < x[1]) ok = false;
if (ok) taken.add(x);
}
return taken.size();
}
public static void main(String[] args) {
int[][] a = {{1, 5}, {4, 7}, {6, 10}};
int[][] b = {{0, 10}, {1, 2}, {3, 4}};
Comparator<int[]> shortest = Comparator.comparingInt(x -> x[1] - x[0]);
Comparator<int[]> earliest = Comparator.comparingInt(x -> x[0]);
System.out.println("shortest first: " + greedy(a, shortest));
System.out.println("earliest start: " + greedy(b, earliest));
}
}
shortest first: 1
earliest start: 1
Both inputs can host 2. Shortest first took [4, 7], which clashes with both others. Earliest start took [0, 10], the whole day.
The key insight: take the booking that ENDS first
- The event that ends first gives the hall back soonest. Take it.
- Exchange argument: in any best plan, replace its first event with ours. Ours ends no later, so it can't clash with the rest of that plan: same count, still optimal. Repeat on what's left.
- Then keep taking the next event that starts at or after the last taken end.
By hand (sorted by end): [1,4] ✓, [3,5] ✗, [0,6] ✗, [5,7] ✓, [3,9] ✗, [5,9] ✗, [6,10] ✗, [8,11] ✓, [8,12] ✗, [2,14] ✗, [12,16] ✓ → 4.
Solution in Java
import java.util.*;
public class Main {
static int maxEvents(int[][] events) {
int[][] e = events.clone();
Arrays.sort(e, (x, y) -> Integer.compare(x[1], y[1]));
int count = 0, lastEnd = Integer.MIN_VALUE;
for (int[] x : e)
if (x[0] >= lastEnd) {
count++;
lastEnd = x[1];
}
return count;
}
public static void main(String[] args) {
int[][] hall = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9},
{6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};
System.out.println(maxEvents(hall));
int[][] a = {{1, 5}, {4, 7}, {6, 10}};
int[][] b = {{0, 10}, {1, 2}, {3, 4}};
System.out.println(maxEvents(a) + " " + maxEvents(b));
System.out.println(maxEvents(new int[][]{}));
System.out.println(maxEvents(new int[][]{{1, 2}, {2, 3}}));
}
}
4
2 2
0
2
Integer.compare, notx[1] - y[1]: subtraction can overflow for huge times and sort wrongly.events.clone()keeps the caller's array unchanged (the rows are shared, but we only reorder them).
The 30 bookings that timed out: 17 events, 24 ms. Ten lakh bookings: 1000000 bookings: 252064 events, 1734 ms (mostly the sort; times vary).
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Activity selection: sort by end time, take every event that starts at or after the last taken end.
int maxEvents(vector<pair<int, int>> ev) {
sort(ev.begin(), ev.end(), [](auto& a, auto& b) { return a.second < b.second; });
int count = 0;
long long lastEnd = LLONG_MIN;
for (auto [s, e] : ev)
if (s >= lastEnd) { count++; lastEnd = e; }
return count;
}
int main() {
cout << maxEvents({{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}}) << "\n";
cout << maxEvents({{1, 5}, {4, 7}, {6, 10}}) << " " << maxEvents({{0, 10}, {1, 2}, {3, 4}}) << "\n";
cout << maxEvents({}) << "\n";
cout << maxEvents({{1, 2}, {2, 3}}) << "\n";
}
4
2 2
0
2
The same solution in Python
# Activity selection: earliest finish first.
def max_events(events):
count, last_end = 0, float("-inf")
for s, e in sorted(events, key=lambda x: x[1]):
if s >= last_end:
count += 1
last_end = e
return count
hall = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(max_events(hall))
print(max_events([(1, 5), (4, 7), (6, 10)]), max_events([(0, 10), (1, 2), (3, 4)]))
print(max_events([]))
print(max_events([(1, 2), (2, 3)]))
4
2 2
0
2
Part 2: Jump Game I and II
Problem
Stones in a line; nums[i] is the most stones you can jump forward from stone i. You start on stone 0.
- Jump Game (LeetCode 55): can you reach the last stone?
- Jump Game II (LeetCode 45): the fewest jumps to reach it (LeetCode guarantees it's reachable).
| nums | Jump Game | Jump Game II |
|---|---|---|
[2, 3, 1, 1, 4] |
true |
2 (0 → 1 → 4) |
[3, 2, 1, 0, 4] |
false (stuck at the 0) |
|
[2, 3, 0, 1, 4] |
true |
2 |
[0] |
true (already there) |
0 |
Constraints: 1 ≤ n ≤ 10^4, 0 ≤ nums[i] ≤ 10^5 (LeetCode 55); n ≤ 10^4, nums[i] ≤ 1000 (LeetCode 45).
Obvious idea: try every jump, recursively
import java.util.*;
public class Main {
static boolean canJump(int[] nums) {
return from(nums, 0);
}
static boolean from(int[] nums, int i) {
if (i >= nums.length - 1) return true;
for (int step = 1; step <= nums[i]; step++)
if (from(nums, i + step)) return true;
return false;
}
public static void main(String[] args) {
System.out.println(canJump(new int[]{2, 3, 1, 1, 4}));
System.out.println(canJump(new int[]{3, 2, 1, 0, 4}));
}
}
true
false
On 42 stones 40, 39, …, 1, 0, 1 (every stone reaches the 0, nothing gets past it): Time Limit Exceeded: it tries every way of hopping across 40 stones, 2^40 ≈ 1.1 lakh crore paths.
The key insight: only the farthest reach matters
We don't care how we got somewhere. Keep far, the farthest stone reachable so far. Walk the stones left to right: if stone i is beyond far, we can't even stand on it: false. Otherwise stretch far to i + nums[i].
| i | nums[i] | far before | far after |
|---|---|---|---|
| 0 | 2 | 0 | 2 |
| 1 | 3 | 2 | 4 |
| 2 | 1 | 4 | 4 |
| … | 4 ≥ 4: true |
For [3, 2, 1, 0, 4]: far stays 3, and stone 4 is beyond it: false.
Solution in Java: Jump Game
import java.util.*;
public class Main {
static boolean canJump(int[] nums) {
int far = 0;
for (int i = 0; i < nums.length; i++) {
if (i > far) return false;
far = Math.max(far, i + nums[i]);
}
return true;
}
public static void main(String[] args) {
System.out.println(canJump(new int[]{2, 3, 1, 1, 4}));
System.out.println(canJump(new int[]{3, 2, 1, 0, 4}));
System.out.println(canJump(new int[]{0}));
System.out.println(canJump(new int[]{0, 1}));
}
}
true
false
true
false
The 42 stones that timed out: false, 0 ms.
Jump Game II: BFS levels without a queue
One jump from stone 0 reaches stones 1..nums[0]: level 1. Everything those reach is level 2, and so on. Each level is one contiguous stretch of stones, so we only need two numbers: end (last stone of the current level) and far (farthest stone of the next level). Walking past end means one more jump.
import java.util.*;
public class Main {
static int jump(int[] nums) {
int jumps = 0, end = 0, far = 0;
for (int i = 0; i < nums.length - 1; i++) {
far = Math.max(far, i + nums[i]);
if (i == end) {
jumps++;
end = far;
}
}
return jumps;
}
public static void main(String[] args) {
System.out.println(jump(new int[]{2, 3, 1, 1, 4}));
System.out.println(jump(new int[]{2, 3, 0, 1, 4}));
System.out.println(jump(new int[]{0}));
}
}
2
2
0
On one crore random stones (1..5 each): 2902226 jumps over 10000000 stones, 28 ms (times vary).
The same Jump Game solutions in C++
#include <bits/stdc++.h>
using namespace std;
// Jump Game (LeetCode 55): keep the farthest reachable index.
bool canJump(const vector<int>& nums) {
int far = 0;
for (int i = 0; i < (int)nums.size(); i++) {
if (i > far) return false;
far = max(far, i + nums[i]);
}
return true;
}
// Jump Game II (LeetCode 45): BFS levels; end = last index of this level, far = farthest of the next.
int jump(const vector<int>& nums) {
int jumps = 0, end = 0, far = 0;
for (int i = 0; i + 1 < (int)nums.size(); i++) {
far = max(far, i + nums[i]);
if (i == end) { jumps++; end = far; }
}
return jumps;
}
int main() {
cout << boolalpha << canJump({2, 3, 1, 1, 4}) << " " << canJump({3, 2, 1, 0, 4}) << " " << canJump({0}) << "\n";
cout << jump({2, 3, 1, 1, 4}) << " " << jump({2, 3, 0, 1, 4}) << " " << jump({0}) << "\n";
}
true false true
2 2 0
The same Jump Game solutions in Python
# Jump Game (LeetCode 55) and Jump Game II (LeetCode 45), both greedy, one pass.
def can_jump(nums):
far = 0
for i, x in enumerate(nums):
if i > far:
return False
far = max(far, i + x)
return True
def jump(nums):
jumps = end = far = 0
for i in range(len(nums) - 1):
far = max(far, i + nums[i])
if i == end:
jumps += 1
end = far
return jumps
print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]), can_jump([0]))
print(jump([2, 3, 1, 1, 4]), jump([2, 3, 0, 1, 4]), jump([0]))
True False True
2 2 0
Three real bugs
Bug 1: > instead of >= (touching events)
if (x[0] > lastEnd) on [[1, 2], [2, 3]]:
1
Should be 2: the second event starts exactly when the first ends, which is allowed.
Bug 2: no "stuck" check in Jump Game
Without if (i > far) return false;:
true
true
Example 2 should be false: the loop stood on stone 4, which nobody can reach, and used its jump.
Bug 3: looping to the last index in Jump Game II
for (int i = 0; i < nums.length; i++) on [2, 3, 1, 1, 4]:
3
Should be 2. On the last stone, i == end, so it counted a jump from the goal.
When does greedy work?
- When you can prove that one local choice is always safe: an exchange argument (swap it into any optimal answer) or a "stays ahead" argument (after every step, greedy is at least as far as any other plan; Jump Game's
far). - When a single counterexample breaks the rule, the problem usually needs dynamic programming instead (episode 62 onwards). Example: activity selection where events have different fees (weighted interval scheduling) is DP, not greedy.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Every subset of bookings | O(2ⁿ · n²) | O(1) | 30 bookings: Time Limit Exceeded |
| Shortest first / earliest start | O(n²) here | O(n) | wrong answers |
| Earliest finish first | O(n log n) | O(n) (the copy) | 10 lakh bookings: ~1.7 s |
| Jump recursion | exponential | O(n) recursion | 42 stones: Time Limit Exceeded |
| Jump Game greedy | O(n) | O(1) | instant |
| Jump Game II levels | O(n) | O(1) | 1 crore stones: 28 ms |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Shortest / earliest start first | 1 instead of 2 |
a greedy rule with no proof | earliest end first |
x[0] > lastEnd |
1 instead of 2 |
touching events are allowed | x[0] >= lastEnd |
No i > far check |
true instead of false |
used an unreachable stone | if (i > far) return false |
| Loop to the last index (Jump II) | 3 instead of 2 |
a jump from the goal | i < nums.length - 1 |
(x, y) -> x[1] - y[1] |
wrong order on huge values | int overflow |
Integer.compare(x[1], y[1]) |
| Greedy on weighted events | a lower total fee | the exchange argument fails | dynamic programming |
Mini project: the hall's booking plan
Print which bookings the owner accepts and why the others are declined.
import java.util.*;
public class Main {
// Mini project: earliest finish first, printing every accept and decline.
public static void main(String[] args) {
String[] who = {"Sharma wedding", "Book club", "Iyer reception", "Kids' party", "Office offsite", "Yoga class", "Mehendi"};
int[][] t = {{9, 13}, {10, 11}, {12, 18}, {13, 15}, {11, 17}, {15, 16}, {16, 20}};
Integer[] idx = new Integer[who.length];
for (int i = 0; i < idx.length; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Integer.compare(t[a][1], t[b][1]));
int lastEnd = Integer.MIN_VALUE, count = 0;
for (int i : idx) {
String slot = String.format("%2d:00-%2d:00", t[i][0], t[i][1]);
if (t[i][0] >= lastEnd) {
System.out.println("accept " + slot + " " + who[i]);
lastEnd = t[i][1];
count++;
} else System.out.println("decline " + slot + " " + who[i] + " (hall busy until " + lastEnd + ":00)");
}
System.out.println(count + " events");
}
}
accept 10:00-11:00 Book club
decline 9:00-13:00 Sharma wedding (hall busy until 11:00)
accept 13:00-15:00 Kids' party
accept 15:00-16:00 Yoga class
decline 11:00-17:00 Office offsite (hall busy until 16:00)
decline 12:00-18:00 Iyer reception (hall busy until 16:00)
accept 16:00-20:00 Mehendi
4 events
Practice
1. Non-overlapping Intervals (LeetCode 435). Fewest intervals to remove so the rest don't overlap.
Solution
n - maxEvents, with earliest finish first.
# Non-overlapping Intervals (LeetCode 435): remove = n - (most non-overlapping, earliest finish first).
def erase_overlap_intervals(intervals):
keep, last_end = 0, float("-inf")
for s, e in sorted(intervals, key=lambda x: x[1]):
if s >= last_end:
keep += 1
last_end = e
return len(intervals) - keep
print(erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]))
print(erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]))
print(erase_overlap_intervals([[1, 2], [2, 3]]))
1
2
0
2. Minimum Number of Arrows to Burst Balloons (LeetCode 452). Balloons are intervals [x1, x2] (closed: touching ones share a point). Fewest vertical arrows to burst all.
Solution
Sort by end; shoot at the end of the first balloon; every balloon starting at or before that point is burst.
import java.util.*;
public class Main {
// Minimum Arrows (LeetCode 452): sort by end; a new arrow when a balloon starts after the last arrow.
static int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 0;
long arrow = Long.MIN_VALUE;
for (int[] p : points)
if (p[0] > arrow) { arrows++; arrow = p[1]; }
return arrows;
}
public static void main(String[] args) {
System.out.println(findMinArrowShots(new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}}));
System.out.println(findMinArrowShots(new int[][]{{1, 2}, {3, 4}, {5, 6}, {7, 8}}));
System.out.println(findMinArrowShots(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}}));
}
}
2
4
2
Here touching balloons do share a point (p[0] > arrow, strictly), unlike today's half-open bookings.
3. Meeting Rooms II (the fewest halls for all requests). Hint: sort by start; keep a min-heap of end times; if the earliest-ending room is free (end ≤ start), reuse it, else open a new room. The heap's size at the end is the answer.
4. Jump Game III (LeetCode 1306). From i you may jump to i + arr[i] or i - arr[i]; can you reach any index with value 0? Hint: it's BFS/DFS on an implicit graph (episode 57), not greedy.
Quick quiz
Bookings [1,3] [2,5] [3,4] [4,7] [5,6] [6,8]. How many events fit? A) 4 B) 3 C) 5 D) 2
Answer
A) 4. By end time: [1,3] ✓, [3,4] ✓, [2,5] ✗, [5,6] ✓, [4,7] ✗, [6,8] ✓.
Interview questions
- What is a greedy algorithm? One that makes the best-looking choice at each step and never revisits it.
- Why earliest finish, not shortest or earliest start? Earliest finish leaves the most room; the exchange argument proves it. The others have 3-interval counterexamples.
- What is the exchange argument? Take any optimal solution, replace one of its choices with the greedy choice, and show it stays valid and optimal.
- How is LeetCode 435 related? Minimum removals =
n− maximum non-overlapping set. - Jump Game in O(n)? Track
far; fail wheni > far. - Why is Jump Game II a BFS? Positions reachable in
kjumps form levelk; each level is a contiguous range, soendandfarreplace the queue. - When does greedy fail? When a locally best choice can hurt later, for example weighted intervals or coin change with odd coins: use DP.
Glossary
| Term | Meaning |
|---|---|
| Greedy algorithm | Best choice now, never undone |
Interval [start, end) |
From start up to, not including, end |
| Overlap | Each starts before the other ends |
| Touching | One ends exactly when the other starts (allowed) |
| Subset / bitmask | A selection of items / an int whose bits mark the selection |
| Counterexample | One input that breaks a rule |
| Exchange argument | Proof by swapping the greedy choice into an optimal answer |
| Activity selection | Most non-overlapping intervals |
far (reach) |
Farthest index reachable so far |
| BFS level | Positions reachable with the same number of jumps |
Summary
- Greedy = best choice now, never undo. It needs a proof; one counterexample kills a rule.
- Activity selection: earliest finish first,
O(n log n); shortest-first and earliest-start-first are traps. - Jump Game: keep
far; stuck wheni > far. Jump Game II: count BFS levels withendandfar. BothO(n). - Watch for:
>vs>=on touching events, the missing stuck check, and jumping from the goal. - Next episode: gas station and task scheduler, two more greedy classics with one-line proofs.