Weighted Interval Scheduling: Forward and Backward Recursion

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

- Sort jobs by end time

- For each job i, compute p[i]: the last non-overlapping job before i

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 startsUse binary search on the end times.

Option 2: Forward Recursion (Alternative)

Strategy

- Sort jobs by start time

- For each job i, compute p[i]: the first job that starts after i ends

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 endsUse binary search on the start times.

Summary

ApproachSorted Byp[i] DefinitionRecurrenceFinal ResultBackward RecursionEnd timeLast compatible before iW[i] = max(w[i] + W[p[i]], W[i−1])W[n]Forward RecursionStart timeNext compatible after iW[i] = max(w[i] + W[p[i]], W[i+1])W[0]

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