Maximum Total Value of Covered Indices - Solution & Explanation

Problem Overview: You are given an array where each index has a value and a list of intervals. Choosing an interval covers all indices within its range. The goal is to pick intervals so the total value of the covered indices is maximized, typically under the constraint that intervals cannot overlap.

Approach 1: Brute Force Subset Enumeration (Exponential Time)

The most direct idea is to try every subset of intervals. For each subset, check if the intervals overlap and compute the total value of the indices they cover. You can precompute prefix sums of the array so that the value of an interval [l, r] is calculated in O(1). This approach requires evaluating up to 2^m subsets where m is the number of intervals, leading to O(2^m * m) time and O(1) extra space. It quickly becomes impractical but helps illustrate the decision process behind selecting compatible intervals.

Approach 2: Dynamic Programming with Interval Sorting (O(m^2))

First compute prefix sums of the value array so the value of each interval can be obtained in constant time. Sort intervals by their ending index. Let dp[i] represent the maximum value achievable considering the first i intervals. For each interval i, you either skip it or take it and add its value to the best non-overlapping interval before it. Finding the previous compatible interval requires scanning backward, which results in O(m^2) time and O(m) space. This approach clearly demonstrates the structure of the optimal subproblem.

Approach 3: Weighted Interval Scheduling with Binary Search (O(m log m))

The optimal solution improves the DP transition. After sorting intervals by end index, use binary search to find the last interval whose end is strictly before the current interval's start. Prefix sums still provide the value of each interval in O(1). The transition becomes dp[i] = max(dp[i-1], value(i) + dp[prev]), where prev is found with binary search. Sorting takes O(m log m) and each DP step performs one binary search, resulting in O(m log m) time and O(m) space. This pattern is the classic weighted interval scheduling technique often seen in dynamic programming and interval problems, combined with binary search for fast compatibility checks.

Recommended for interviews: Interviewers expect the weighted interval scheduling solution with binary search. Starting with the brute-force idea shows you understand the search space, but transitioning to DP with sorted intervals and binary search demonstrates strong problem decomposition and optimization skills.