397. Maximum Score of Non-overlapping Intervals

This is weighted interval scheduling capped at 4 picks: sort by start, and for each interval jump (via binary search) to the first interval that starts after it ends, choosing take-vs-skip while tracking both the best weight and the lexicographically smallest index list on ties.

Idea

This is the classic weighted interval scheduling problem with two twists: you may take at most 4 intervals, and among all maximum-weight choices you must return the lexicographically smallest list of original indices. "Non-overlapping" is strict — touching endpoints (r_i == l_j) still counts as overlapping — so an interval with right endpoint r may only be followed by one whose left endpoint is strictly greater than r.

Algorithm

1. Pair every interval with its original index, then sort by left endpoint. Call the sorted starts starts.
2. Precompute nxt[p] = the first sorted position whose start is > r of the interval at position p, using binary search (upper_bound on starts). From position p, nxt[p] is where a compatible next interval can begin.
3. Define dp[p][k] = the best answer using intervals from sorted position p onward while choosing at most k of them. Each entry stores a pair (total_weight, sorted_index_list).
4. Fill dp from p = n-1 down to 0 and k = 0..4. Two choices:
   • Skip p: dp[p+1][k].
   • Take p (only if k > 0): weight[p] + dp[nxt[p]][k-1], appending the original index and re-sorting. Keep whichever is better: higher weight wins; on a tie, the lexicographically smaller sorted index list wins.
5. The answer is dp[0][4]'s index list.

Worked example

intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]] (original indices 0..5).

Sorted by start: 0:[1,3,2], 2:[1,5,5], 1:[4,5,2], 4:[6,7,1], 3:[6,9,3], 5:[8,9,1].

• Interval 2 = [1,5,5] ends at 5, so its nxt skips past every interval starting at ≤ 5 and lands on [6,7,1]. Taking 2 then the best of the tail gives weight 5 + 3 = 8 by adding [6,9,3] (index 3) → candidate indices [2,3], weight 8.
• Any choice starting with index 0 ([1,3,2]) can chain more intervals but tops out below weight 8, and choices reaching weight 8 a different way do not beat [2,3] lexicographically.

Maximum score is 8, achieved by indices [2,3] → the answer.

Complexity

• Time: O(n log n) — sorting plus one binary search per interval; the DP is O(n · K) with K = 4.
• Space: O(n · K) for the DP table (each cell holds at most 4 indices).

import java.util.*;

class Solution {
    public int[] maximumWeight(int[][] intervals) {
        int n = intervals.length;
        // Sort interval indices by left endpoint.
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        java.util.Arrays.sort(order, (a, b) -> Integer.compare(intervals[a][0], intervals[b][0]));

        int[] starts = new int[n];
        for (int p = 0; p < n; p++) starts[p] = intervals[order[p]][0];

        // nxt[p] = first sorted position whose start is strictly greater than the
        // right endpoint of the interval at sorted position p (boundary touch = overlap).
        int[] nxt = new int[n];
        for (int p = 0; p < n; p++) {
            nxt[p] = upperBound(starts, intervals[order[p]][1]);
        }

        final int K = 4;
        long[][] w = new long[n + 1][K + 1];
        List<Integer>[][] idx = new List[n + 1][K + 1];
        for (int k = 0; k <= K; k++) idx[n][k] = new ArrayList<>();

        for (int p = n - 1; p >= 0; p--) {
            for (int k = 0; k <= K; k++) {
                long bestW = w[p + 1][k];
                List<Integer> bestIdx = idx[p + 1][k];
                if (k > 0) {
                    long takeW = (long) intervals[order[p]][2] + w[nxt[p]][k - 1];
                    List<Integer> takeIdx = new ArrayList<>(idx[nxt[p]][k - 1]);
                    takeIdx.add(order[p]);
                    Collections.sort(takeIdx);
                    if (takeW > bestW || (takeW == bestW && lexLess(takeIdx, bestIdx))) {
                        bestW = takeW;
                        bestIdx = takeIdx;
                    }
                }
                w[p][k] = bestW;
                idx[p][k] = bestIdx;
            }
        }

        List<Integer> ans = idx[0][K];
        int[] res = new int[ans.size()];
        for (int i = 0; i < res.length; i++) res[i] = ans.get(i);
        return res;
    }

    // First index whose value is strictly greater than target.
    private int upperBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // True if list a is lexicographically smaller than list b (both sorted).
    private boolean lexLess(List<Integer> a, List<Integer> b) {
        int m = Math.min(a.size(), b.size());
        for (int i = 0; i < m; i++) {
            int c = Integer.compare(a.get(i), b.get(i));
            if (c != 0) return c < 0;
        }
        return a.size() < b.size();
    }
}