Maximum Profit in Job Scheduling

We have jobs (start, end, profit). We want to pick a subset of non-overlapping jobs to maximize total profit.

Example:

• Job 1: [1, 3], Profit 50
• Job 2: [2, 4], Profit 10
• Job 3: [3, 5], Profit 40
• If we pick Job 1, we can't pick Job 2 (overlap). We CAN pick Job 3.
• Total: 90.

1. Sort jobs by End Time.
2. Define dp[i] = Max profit using subset of first i jobs.
3. For Job i (index i-1 in sorted list):
   • Include: Profit p[i] + dp[index of latest job ending <= start[i]].
   • Exclude: dp[i-1].
4. dp[i] = max(Include, Exclude).
5. Use Binary Search to efficiently find the "latest non-conflicting job".

Observe the decision process. Sorting by end time allows us to linearize the problem. The visualizer shows finding the previous compatible job (green).

Click 'Randomize' to generate new jobs.