Maximum Score of Non-overlapping Intervals

• Initialize max_score = 0 and best_indices = [].
• Iterate through k from 1 to 4.
• For each k, generate all combinations of k distinct indices from 0 to n-1.
• For each combination of indices:
  • Fetch the corresponding intervals.
  • Check if these k intervals are mutually non-overlapping. This check takes O(k^2) time.
  • If they are non-overlapping:
    • Calculate the sum of their weights.
    • If the current sum is greater than max_score, update max_score with the new sum and best_indices with the current combination of indices (sorted).
    • If the current sum is equal to max_score, compare the current combination of indices (sorted) with best_indices and update best_indices if the current one is lexicographically smaller.

The brute-force method is the most straightforward way to conceptualize the problem. We need to find the best subset of at most 4 intervals. We can break this down by the size of the subset, k.

For each k in {1, 2, 3, 4}:

1. Generate all unique combinations of k intervals from the input list.
2. For each combination, verify the non-overlapping constraint. A set of intervals is non-overlapping if for any pair of intervals [l1, r1] and [l2, r2] in the set, either r1 < l2 or r2 < l1.
3. If the non-overlapping constraint is met, compute the sum of weights for the intervals in the current combination.
4. Compare this sum with the maximum score found so far. If the current score is higher, we've found a new best set. If the scores are equal, we compare the lists of indices lexicographically and keep the smaller one.

This process ensures we check every possibility, guaranteeing we find the optimal answer. However, the number of combinations, especially for k=4, is enormous (C(n, 4) is on the order of n^4), making this approach computationally infeasible for the given constraints.

• Augment each interval with its original index: (start, end, weight, original_index).
• Sort the intervals based on their end times. Use start times as a tie-breaker.
• Create a DP table dp[n+1][5]. dp[i][k] will store a pair: {long score, List<Integer> indices}.
• Initialize dp[0][k] with score 0 and an empty list for all k.
• Iterate i from 1 to n:
  • Let current_interval be the (i-1)-th interval in the sorted list.
  • Iterate k from 1 to 4:
    • Option 1 (Don't take current_interval): The result is dp[i-1][k].
    • Option 2 (Take current_interval):
      • Find the rightmost interval p in 0...i-2 that ends before current_interval starts. This can be done with binary search on the end times, taking O(log i) time.
      • The previous state is dp[p+1][k-1].
      • The new result is {current_interval.weight + dp[p+1][k-1].score, ...}.
    • Compare the results from Option 1 and Option 2. Choose the one with the higher score. If scores are tied, choose the one with the lexicographically smaller index list. Store this in dp[i][k].
• After filling the table, find the best result among dp[n][1], dp[n][2], dp[n][3], dp[n][4] by applying the same comparison logic.
• Return the list of indices from the final best result.

This approach systematically builds the optimal solution. Here's a detailed breakdown:

1. Data Preparation: We first encapsulate the interval data (start, end, weight) along with its original index into a custom object or struct. This is crucial for tracking the indices for the final output.

2. Sorting: The intervals are sorted primarily by their end points in ascending order. If end points are equal, we can use start points as a secondary sorting criterion. This ordering is key to the DP transition's efficiency.

3. DP State: We define dp[i][k] to be the optimal result (containing both the maximum score and the corresponding lexicographically smallest list of indices) for choosing exactly k non-overlapping intervals from the first i intervals of our sorted list.

4. DP Transition: We fill the dp table iteratively. For each interval i and count k, we decide whether to include interval i in our set:

   • Case 1: Exclude interval i. The best we can do is the optimal solution for k intervals using the first i-1 intervals, which is dp[i-1][k].
   • Case 2: Include interval i. To do this, we must have chosen k-1 intervals that are all non-overlapping with interval i. Since intervals are sorted by end times, all such predecessors must end before interval i begins. We need to find the optimal solution for k-1 intervals that satisfies this. We can use binary search on the sorted intervals 0...i-1 to find the index p of the last interval that ends before intervals[i].start. The best result for the k-1 predecessors is then given by dp[p+1][k-1]. We add intervals[i].weight to its score and intervals[i].original_index to its index list.

5. Decision: We compare the results from Case 1 and Case 2. The one with the higher score wins. In case of a tie in score, the one with the lexicographically smaller index list is chosen. This result is stored in dp[i][k].

6. Final Result: After the DP table is fully computed, the problem asks for at most 4 intervals. So, we find the overall best result by comparing dp[n][1], dp[n][2], dp[n][3], and dp[n][4] using the same score/lexicographical comparison logic.

1import java.util.*;2 3class Solution {4    // Helper class to store result pair5    static class Result {6        long score;7        List<Integer> indices;8 9        Result(long score, List<Integer> indices) {10            this.score = score;11            this.indices = indices;12        }13    }14 15    // Helper class for intervals16    static class Interval {17        int start, end, weight, id;18 19        Interval(int start, int end, int weight, int id) {20            this.start = start;21            this.end = end;22            this.weight = weight;23            this.id = id;24        }25    }26 27    public int[] maxScore(int[][] intervals) {28        int n = intervals.length;29        Interval[] sortedIntervals = new Interval[n];30        for (int i = 0; i < n; i++) {31            sortedIntervals[i] = new Interval(intervals[i][0], intervals[i][1], intervals[i][2], i);32        }33 34        // Sort by end time, then start time35        Arrays.sort(sortedIntervals, (a, b) -> {36            if (a.end != b.end) {37                return Integer.compare(a.end, b.end);38            }39            return Integer.compare(a.start, b.start);40        });41 42        Result[][] dp = new Result[n + 1][5];43 44        for (int k = 0; k <= 4; k++) {45            dp[0][k] = new Result(0, new ArrayList<>());46        }47 48        for (int i = 1; i <= n; i++) {49            dp[i][0] = new Result(0, new ArrayList<>());50            Interval current = sortedIntervals[i - 1];51 52            for (int k = 1; k <= 4; k++) {53                // Option 1: Don't include current interval54                Result res1 = dp[i - 1][k];55 56                // Option 2: Include current interval57                // Find the last interval j < i-1 that doesn't overlap with current58                int p = binarySearch(sortedIntervals, i - 1, current.start);59                60                Result prevRes = dp[p + 1][k - 1];61                long newScore = current.weight + prevRes.score;62                List<Integer> newIndices = new ArrayList<>(prevRes.indices);63                newIndices.add(current.id);64                Collections.sort(newIndices); // Keep it sorted for lexicographical comparison65                Result res2 = new Result(newScore, newIndices);66 67                // Compare and choose the better result68                dp[i][k] = better(res1, res2);69            }70        }71 72        Result finalResult = new Result(0, new ArrayList<>());73        for (int k = 1; k <= 4; k++) {74            finalResult = better(finalResult, dp[n][k]);75        }76 77        int[] resultArr = new int[finalResult.indices.size()];78        for (int i = 0; i < finalResult.indices.size(); i++) {79            resultArr[i] = finalResult.indices.get(i);80        }81        return resultArr;82    }83 84    // Returns the index of the rightmost interval ending before start_time85    private int binarySearch(Interval[] intervals, int high, int startTime) {86        int low = 0;87        int ans = -1;88        while (low <= high) {89            int mid = low + (high - low) / 2;90            if (intervals[mid].end < startTime) {91                ans = mid;92                low = mid + 1;93            } else {94                high = mid - 1;95            }96        }97        return ans;98    }99 100    // Compares two results and returns the better one101    private Result better(Result r1, Result r2) {102        if (r1.score > r2.score) {103            return r1;104        }105        if (r2.score > r1.score) {106            return r2;107        }108        // Scores are equal, compare indices lexicographically109        for (int i = 0; i < Math.min(r1.indices.size(), r2.indices.size()); i++) {110            if (r1.indices.get(i) < r2.indices.get(i)) {111                return r1;112            }113            if (r2.indices.get(i) < r1.indices.get(i)) {114                return r2;115            }116        }117        return r1.indices.size() < r2.indices.size() ? r1 : r2;118    }119}