DP with Binary Search Optimization

Problem Statement

You are given an array of n intervals [start, end, profit]. You can select a subset of non-overlapping intervals to maximize total profit.

Two intervals overlap if one starts before the other ends.

Return the maximum profit achievable by selecting non-overlapping intervals.

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= start < end <= 10^9
• 1 <= profit <= 10^4

Example

Input:

intervals = [[1,3,50], [2,5,20], [4,6,70], [6,8,60]]

Output: 180

Explanation: Select intervals [1,3,50] + [4,6,70] + [6,8,60] = 180

Expected Progression

The interviewer expects you to iterate through these solutions:

1. Brute force / Recursion — Try all subsets, O(2^n)
2. Memoization — Sort by end time, for each interval decide include/skip, memo on index
3. Bottom-up DP — Tabulate the decision at each index
4. DP + Binary Search — When including an interval, binary search for the latest non-overlapping previous interval instead of linear scan. Brings it from O(n^2) to O(n log n).

Follow-ups

1. What if you can select at most K intervals (bounded selection)?
2. What if intervals have dependencies — interval B requires interval A to be selected first?
3. Can you solve this in O(n log n) time and O(1) extra space beyond the sort?
4. How does this problem relate to the Longest Increasing Subsequence?