Introduction

In algorithmic problem solving, Dynamic Programming (DP) and Greedy algorithms are two fundamental paradigms used for optimization problems that exhibit optimal substructure. However, a common point of confusion arises when two problems look almost identical on the surface, yet one succumbs to a simple greedy rule while the other requires full-blown dynamic programming.

A classic example is comparing the standard Activity Selection Problem with the Weighted Job Scheduling Problem. Why does picking the earliest finishing activity yield an optimal solution for the former, but completely fail for the latter?

The Core Difference: Optimal Substructure vs. Greedy Choice Property

Both problems exhibit optimal substructure, meaning an optimal solution to the overall problem contains within it optimal solutions to its subproblems.

However, for a greedy algorithm to yield the globally optimal solution, a problem must also satisfy the greedy choice property: a locally optimal choice must always lead to a globally optimal solution without ever needing to reconsider past choices or evaluate alternative subproblems.

Why Greedy Works for Activity Selection

In unweighted Activity Selection, every job has equal value (effectively weight = 1). The goal is simply to maximize the total number of non-overlapping activities.

By choosing the activity that finishes earliest, you leave as much remaining time as possible for subsequent activities. Choosing an activity with a later finish time can never leave more remaining time than choosing one with an earlier finish time. Thus, the greedy choice never restricts your future options more than an alternative choice would, preserving the path to global optimality.

Why Greedy Fails for Weighted Job Scheduling

Now consider Weighted Job Scheduling, where each job i has a start time, end time, and a profit profit[i]. The goal is to maximize total profit.

If you apply the same greedy heuristic—picking the job that finishes earliest—it quickly breaks. Imagine two jobs:

  • Job A: Starts at 1, ends at 2, profit = $10
  • Job B: Starts at 1, ends at 10, profit = $1000

The earliest finishing job is Job A. A greedy algorithm picks Job A, which immediately blocks Job B, resulting in a total profit of $10. However, the true optimal choice is Job B with a profit of $1000.

Even trying other greedy criteria—such as highest profit first, or highest profit-to-duration ratio—leads to straightforward counterexamples. The presence of variable weights creates trade-offs where a local sacrifice in finish time or profit density yields a vastly superior global solution.

The Dynamic Programming Solution

Because the greedy choice property fails, we must explore multiple choices and reuse solutions to overlapping subproblems using Dynamic Programming.

First, sort all jobs by their finish times in non-decreasing order. Define dp[i] as the maximum profit obtainable using a subset of the first i jobs.

For each job i, we have two decisions:

  • Exclude job i: The max profit is dp[i - 1].
  • Include job i: The max profit is profit[i] + dp[last_non_overlapping(i)], where last_non_overlapping(i) is the index of the latest job that finishes before job i starts.

The recurrence relation is:

dp[i] = max(dp[i - 1], profit[i] + dp[last_non_overlapping(i)])

Python Implementation

import bisect

def max_profit_job_scheduling(jobs):
    # Each job in jobs is represented as [start, finish, profit]
    # Sort jobs by finish time
    jobs.sort(key=lambda x: x[1])
    
    n = len(jobs)
    finish_times = [job[1] for job in jobs]
    dp = [0] * n
    dp[0] = jobs[0][2]
    
    for i in range(1, n):
        incl_profit = jobs[i][2]
        
        # Find the latest non-overlapping job using binary search
        idx = bisect.bisect_right(finish_times, jobs[i][0]) - 1
        if idx != -1:
            incl_profit += dp[idx]
        
        dp[i] = max(dp[i - 1], incl_profit)
        
    return dp[-1]

How to Tell If a Problem Needs Greedy or DP

When analyzing an optimization problem, use these guidelines to determine the appropriate approach:

  • Can a local choice irrevocably block a superior global option? If selecting an item limits future possibilities that could offer higher cumulative rewards due to weights or capacities, Greedy will fail. You need Dynamic Programming.
  • Can you prove the Greedy Choice Property using an Exchange Argument? Assume an optimal solution does not include your greedy choice. Can you substitute your greedy choice into that optimal solution without decreasing its overall quality? If yes, Greedy works; if not, DP is required.
  • Are all item values/weights uniform? Unweighted problems (like simple Activity Selection or Unweighted Shortest Path) frequently satisfy greedy choices, whereas adding arbitrary weights or non-linear constraints almost always necessitates Dynamic Programming.