Module 4.3 ⏱ 35 min read ⚡ Optimization & Greedy Patterns

Greedy Algorithms

Master the greedy choice property, optimal substructure, interval scheduling strategies, and linear jump game optimizations.

1. The Greedy Choice Property & Optimal Substructure

A greedy algorithm makes locally optimal choices at each stage with the intent of finding a globally optimum solution. For a greedy strategy to succeed, a problem must possess two core properties:

Greedy Choice Property: A global optimal solution can be assembled by making a locally optimal choice (greedy step) without reconsidering past decisions or exploring all branch states.

Optimal Substructure: An optimal solution to the problem contains optimal solutions to its constituent subproblems, allowing sequential reduction without backtracking overhead.

2. Interval Scheduling & Activity Selection

Interval scheduling requires selecting the maximum number of non-overlapping intervals given start and end times. The canonical greedy strategy sorts intervals by their finish times in ascending order and greedily picks the next activity that starts after or at the finish time of the previously selected activity.

3. Jump Game Problems (Forward Tracking)

Jump games test whether you can reach the end of an array or find the minimum number of steps required, where each element represents your maximum jump length. By tracking the farthest reachable index dynamically during iteration, you achieve optimal linear $O(n)$ time complexity.

// C++ Solution: Jump Game (Greedy Forward Tracking)
#include <vector>
#include <algorithm>

class Solution {
public:
    bool canJump(std::vector<int>& nums) {
        int reachable = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > reachable) return false;
            reachable = std::max(reachable, i + nums[i]);
        }
        return true;
    }
};
            

# Python Solution: Jump Game (Greedy Forward Tracking)
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        reachable = 0
        for i, val in enumerate(nums):
            if i > reachable:
                return False
            reachable = max(reachable, i + val)
        return True
            

// Java Solution: Jump Game (Greedy Forward Tracking)
class Solution {
    public boolean canJump(int[] nums) {
        int reachable = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reachable) return false;
            reachable = Math.max(reachable, i + nums[i]);
        }
        return true;
    }
}
            

4. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for Activity Selection and the Jump Game problems.

Quick Check: Test Your Intuition

Why do we sort intervals by their finish times rather than start times when solving the interval scheduling problem?