Watch the video solution for Maximum Score of Non-overlapping Intervals, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by Programming Live with Larry has 654 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array intervals, where intervals[i] = [li, ri, weighti]. Interval i starts at position li and ends at ri, and has a weight of weighti. You can choose up to 4 non-overlapping intervals. The score of the chosen intervals is defined as the total sum of their weights.
Return the lexicographically smallest array of at most 4 indices from intervals with maximum score, representing your choice of non-overlapping intervals.
Two intervals are said to be non-overlapping if they do not share any points. In particular, intervals sharing a left or right boundary are considered overlapping.
Example 1:
Input: intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
Output: [2,3]
Explanation:
You can choose the intervals with indices 2, and 3 with respective weights of 5, and 3.
Example 2:
Input: intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]
Output: [1,3,5,6]
Explanation:
You can choose the intervals with indices 1, 3, 5, and 6 with respective weights of 7, 6, 3, and 5.
Constraints:
1 <= intevals.length <= 5 * 104intervals[i].length == 3intervals[i] = [li, ri, weighti]1 <= li <= ri <= 1091 <= weighti <= 109Problem Overview: You receive a list of intervals where each interval has a start time, end time, and score. The goal is to select a subset of non-overlapping intervals that maximizes the total score. If two intervals overlap in time, you can only choose one.
Approach 1: Brute Force Subset Enumeration (O(2^n) time, O(n) space)
The simplest idea is to generate every possible subset of intervals and check whether the chosen intervals overlap. For each valid subset, compute the total score and keep the maximum. Checking overlap requires sorting the chosen intervals and verifying adjacent ranges. This approach demonstrates the core constraint but becomes infeasible even for moderate n because the number of subsets grows exponentially.
Approach 2: Dynamic Programming with Sorting (O(n^2) time, O(n) space)
First sort intervals by their ending time. Define dp[i] as the maximum score achievable considering intervals up to index i. For each interval, iterate backward to find the latest interval that does not overlap. The recurrence becomes dp[i] = max(dp[i-1], score[i] + dp[prev]), where prev is the last compatible interval. This reduces the exponential search to polynomial time by reusing results. The idea mirrors classic weighted interval scheduling using dynamic programming.
Approach 3: DP + Binary Search (O(n log n) time, O(n) space)
Instead of scanning backward to locate the previous non-overlapping interval, store the sorted end times and use binary search. For each interval i, binary search the rightmost interval whose end time is less than or equal to the current start time. Combine its DP value with the current score. The recurrence remains the same, but the lookup becomes O(log n) rather than O(n). Sorting the intervals first using sorting ensures the DP state transitions are valid.
This approach scales well for large inputs. Each interval contributes a constant DP update and a binary search lookup.
Recommended for interviews: The DP with binary search solution is the expected approach. Starting from the brute force idea shows you understand the overlap constraint. Moving to sorted intervals and DP demonstrates the classic weighted scheduling optimization. Using binary search to locate the previous compatible interval reduces the complexity to O(n log n), which is the standard optimal solution interviewers look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n) | O(n) | Conceptual understanding or very small input sizes |
| DP with Backward Scan | O(n^2) | O(n) | Moderate input sizes where implementation simplicity matters |
| DP + Binary Search (Weighted Interval Scheduling) | O(n log n) | O(n) | Optimal solution for large datasets and typical interview expectation |