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".