# Maximum Score of Non-overlapping Intervals
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-score-of-non-overlapping-intervals)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-of-non-overlapping-intervals
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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 * 104`
* `intervals[i].length == 3`
* `intervals[i] = [li, ri, weighti]`
* `1 <= li <= ri <= 109`
* `1 <= weighti <= 109`

# Approaches
## Brute-Force Combinations
This approach involves checking every possible valid selection of intervals. We can choose 1, 2, 3, or 4 intervals. The method iterates through all combinations of `k` intervals (for `k` from 1 to 4), checks if they are non-overlapping, and calculates their total weight. It keeps track of the combination that yields the maximum score, adhering to the lexicographical requirement for tie-breaking.
**Time:** O(n^4). The dominant part is generating and checking combinations of 4 intervals. The number of combinations of 4 from `n` is `C(n, 4) ≈ n^4 / 24`. For each combination, we perform an `O(k^2)` check for overlaps. Thus, the total complexity is roughly `O(n^4 * k^2)`, which is dominated by `n^4`. · **Space:** O(k), where k is the number of chosen intervals (at most 4). This space is used to store the current combination of indices.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer if it runs to completion.
**Cons:** Extremely inefficient and will not pass within the time limits for the given constraints.; The number of combinations `C(n, k)` grows very rapidly with `n`.
### Explanation
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.
### Algorithm
- 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.

## Dynamic Programming on End-Time Sorted Intervals
A more efficient solution uses dynamic programming. The key insight is to process intervals in a sorted order and build up solutions for choosing `k` intervals based on optimal solutions for `k-1` intervals. By sorting intervals by their end times, we can efficiently find the latest possible non-overlapping predecessor for any given interval using binary search.
**Time:** O(n * k * (log n + k)). Sorting takes `O(n log n)`. The nested loops run `n * k` times. Inside the loop, the binary search takes `O(log n)`, and creating/comparing index lists takes `O(k)`. With `k=4`, this is `O(n * (log n + 4))`, which simplifies to `O(n log n)`. · **Space:** O(n * k^2). The DP table has `(n+1) x (k+1)` entries. Each entry stores a `Result` object, which contains a list of up to `k` indices. With `k=4`, the space complexity is `O(16n)`, which simplifies to `O(n)`.
**Pros:** Highly efficient, with a time complexity that handles the given constraints well.; Systematically finds the optimal solution by building upon smaller subproblems.; Correctly handles the lexicographical tie-breaking rule.
**Cons:** More complex to implement than a brute-force approach.; Requires careful handling of DP states, which include both a score and a list of indices.; The binary search and logic for choosing predecessors must be implemented correctly.
### Explanation
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.

```java
import java.util.*;

class Solution {
    // Helper class to store result pair
    static class Result {
        long score;
        List<Integer> indices;

        Result(long score, List<Integer> indices) {
            this.score = score;
            this.indices = indices;
        }
    }

    // Helper class for intervals
    static class Interval {
        int start, end, weight, id;

        Interval(int start, int end, int weight, int id) {
            this.start = start;
            this.end = end;
            this.weight = weight;
            this.id = id;
        }
    }

    public int[] maxScore(int[][] intervals) {
        int n = intervals.length;
        Interval[] sortedIntervals = new Interval[n];
        for (int i = 0; i < n; i++) {
            sortedIntervals[i] = new Interval(intervals[i][0], intervals[i][1], intervals[i][2], i);
        }

        // Sort by end time, then start time
        Arrays.sort(sortedIntervals, (a, b) -> {
            if (a.end != b.end) {
                return Integer.compare(a.end, b.end);
            }
            return Integer.compare(a.start, b.start);
        });

        Result[][] dp = new Result[n + 1][5];

        for (int k = 0; k <= 4; k++) {
            dp[0][k] = new Result(0, new ArrayList<>());
        }

        for (int i = 1; i <= n; i++) {
            dp[i][0] = new Result(0, new ArrayList<>());
            Interval current = sortedIntervals[i - 1];

            for (int k = 1; k <= 4; k++) {
                // Option 1: Don't include current interval
                Result res1 = dp[i - 1][k];

                // Option 2: Include current interval
                // Find the last interval j < i-1 that doesn't overlap with current
                int p = binarySearch(sortedIntervals, i - 1, current.start);
                
                Result prevRes = dp[p + 1][k - 1];
                long newScore = current.weight + prevRes.score;
                List<Integer> newIndices = new ArrayList<>(prevRes.indices);
                newIndices.add(current.id);
                Collections.sort(newIndices); // Keep it sorted for lexicographical comparison
                Result res2 = new Result(newScore, newIndices);

                // Compare and choose the better result
                dp[i][k] = better(res1, res2);
            }
        }

        Result finalResult = new Result(0, new ArrayList<>());
        for (int k = 1; k <= 4; k++) {
            finalResult = better(finalResult, dp[n][k]);
        }

        int[] resultArr = new int[finalResult.indices.size()];
        for (int i = 0; i < finalResult.indices.size(); i++) {
            resultArr[i] = finalResult.indices.get(i);
        }
        return resultArr;
    }

    // Returns the index of the rightmost interval ending before start_time
    private int binarySearch(Interval[] intervals, int high, int startTime) {
        int low = 0;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (intervals[mid].end < startTime) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    // Compares two results and returns the better one
    private Result better(Result r1, Result r2) {
        if (r1.score > r2.score) {
            return r1;
        }
        if (r2.score > r1.score) {
            return r2;
        }
        // Scores are equal, compare indices lexicographically
        for (int i = 0; i < Math.min(r1.indices.size(), r2.indices.size()); i++) {
            if (r1.indices.get(i) < r2.indices.get(i)) {
                return r1;
            }
            if (r2.indices.get(i) < r1.indices.get(i)) {
                return r2;
            }
        }
        return r1.indices.size() < r2.indices.size() ? r1 : r2;
    }
}
```
### Algorithm
- 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.