Imagine you’re given a list of jobs. Each job has:

• A start time
• An end time
• A weight (or profit)

Your mission: choose a subset of non-overlapping jobs that maximizes total weight.

This is a classic Dynamic Programming problem: Weighted Interval Scheduling.

Let me walk you through the whole thing — as if I were teaching my past self.

Step 1: Understand the Problem

Given n intervals:

jobs = [
(start1, end1, weight1),
(start2, end2, weight2),
…
]

We need to select a subset of non-overlapping intervals so that their total weight is maximized.

Step 2: Choose Your Approach — Backward vs Forward

There are two valid strategies:

• Backward Recursion: Work from the end of the list.
• Forward Recursion: Work from the start of the list.

Option 1: Backward Recursion (Classic DP)

Strategy

1. Sort jobs by end time
2. For each job i, compute p[i]: the last non-overlapping job before i
3. Build a DP table W[i] where:
   • W[i] = max total weight from first i jobs

How to Compute p[i]

p[i] = index of the last job ending before job i starts
Use binary search on the end times.

Option 2: Forward Recursion (Alternative)

Strategy

1. Sort jobs by start time
2. For each job i, compute p[i]: the first job that starts after i ends
3. Build a DP table W[i] where:
   • W[i] = max total weight from jobs starting at or after i

The recurrence:

W[i] = max(weight[i] + W[p[i]], W[i + 1])

How to Compute p[i]

p[i] = index of the first job starting after job i ends
Use binary search on the start times.

Summary

Approach	Sorted By	p[i] Definition	Recurrence	Final Result
Backward Recursion	End time	Last compatible before i	W[i] = max(w[i] + W[p[i]], W[i−1])	W[n]
Forward Recursion	Start time	Next compatible after i	W[i] = max(w[i] + W[p[i]], W[i+1])	W[0]

Both strategies give you the correct optimal value, just from different directions.