SyntaxPilot
Courses/DSA and Coding Problems/Lesson 59
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 59 of 90

Greedy: activity selection and jump game

queued

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): from start up 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 i says whether request i is 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, not x[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

  1. What is a greedy algorithm? One that makes the best-looking choice at each step and never revisits it.
  2. 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.
  3. 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.
  4. How is LeetCode 435 related? Minimum removals = n − maximum non-overlapping set.
  5. Jump Game in O(n)? Track far; fail when i > far.
  6. Why is Jump Game II a BFS? Positions reachable in k jumps form level k; each level is a contiguous range, so end and far replace the queue.
  7. 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 when i > far. Jump Game II: count BFS levels with end and far. Both O(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.