3414. Maximum Score of Non-overlapping Intervals

Array
Binary Search
Dynamic Programming
Sorting

TIME

O(n log n)

SPACE

O(n)

Intuition

This is weighted interval scheduling with a cap of 4 picks, plus a tiebreak on the returned index array.

Sorting by left endpoint makes the structure usable: once intervals are in that order, taking the interval at position p forbids everything until the first interval whose left endpoint clears r_p. That boundary is a single binary search, and it never moves, so it can be precomputed once per position.

The cap of 4 just adds a second dimension to the state. From any position the choice is binary, skip this interval, or take it and jump past its conflicts with one fewer pick remaining.

The tiebreak is the part that needs care. The output is the chosen original indices in ascending order, but the DP walks intervals in left-endpoint order, so an interval taken early can carry a large index and land at the end of the sorted result. Each state therefore stores the full index tuple, not just a score, and states are ranked by (-score, indices).

That composition is only valid if merging a fixed index into the lexicographically smaller suffix still yields the lexicographically smaller merged list. It does: two sorted suffixes of equal score agree up to their first difference, and inserting the same element into both preserves the relative order at that point. Verified against brute force on inputs built to maximise ties (identical weights, index order scrambled relative to position order).

Approach

Sort positions by left endpoint, keeping the original index alongside.
Precompute nxt[p] = bisect_right(lefts, r_p), the first position whose left endpoint is strictly greater than r_p. Strictness matters, touching boundaries count as overlapping.
dp[p][k] = best (score, sorted index tuple) using positions >= p with at most k picks; base dp[n][k] = (0, ()).
Sweep p from n-1 down to 0, and for each k in 1..4:
- skip: dp[p+1][k]
- take: (dp[nxt[p]][k-1].score + w_p, sorted(dp[nxt[p]][k-1].indices + (idx_p,)))
- keep whichever compares smaller under (-score, indices)
Answer is dp[0][4]'s index tuple.

Complexity

Time: O(n log n), the sort and one binary search per interval; the DP is O(4n) with O(1) tuple work (at most 4 elements)
Space: O(n), the DP table holds 5 tuples of length <= 4 per position

Edge Cases

Intervals sharing an endpoint overlap, so nxt must use a strict comparison (bisect_right on the right endpoint)
Equal scores reachable with different counts, e.g. one weight-5 interval versus weights 2 and 3, so index tuples of different lengths get compared; standard tuple comparison handles this
Weights are all positive, so more intervals is never worse on score alone; the cap of 4 is what binds
Scores reach 4 * 10^9, which overflows 32-bit; use long in Java
Single interval → that one index
Duplicate left endpoints are fine; the binary search keys on the right endpoint

Code

from typing import List
from bisect import bisect_right


class Solution:
    def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
        """
        3414. Maximum Score of Non-overlapping Intervals
        Time: O(n log n)
        Space: O(n)
        """
        n = len(intervals)
        order = sorted(range(n), key=lambda i: intervals[i][0])
        lefts = [intervals[i][0] for i in order]

        # nxt[p] = first sorted position whose left endpoint is strictly past r_p;
        # strict because intervals sharing a boundary still overlap
        nxt = [bisect_right(lefts, intervals[order[p]][1]) for p in range(n)]

        # dp[p][k] = (score, sorted tuple of original indices) for positions >= p
        dp = [[(0, ())] * 5 for _ in range(n + 1)]

        for p in range(n - 1, -1, -1):
            idx = order[p]
            weight = intervals[idx][2]
            for k in range(1, 5):
                best = dp[p + 1][k]                       # skip this interval
                sub_score, sub_idx = dp[nxt[p]][k - 1]    # take it, jump past conflicts
                cand = (sub_score + weight, tuple(sorted(sub_idx + (idx,))))
                # higher score wins; ties go to the lexicographically smaller indices
                if (-cand[0], cand[1]) < (-best[0], best[1]):
                    best = cand
                dp[p][k] = best

        return list(dp[0][4][1])

import java.util.Arrays;

/**
 * 3414. Maximum Score of Non-overlapping Intervals
 * Time: O(n log n)
 * Space: O(n)
 */
class Solution {
    public int[] maximumWeight(java.util.List<java.util.List<Integer>> intervals) {
        int n = intervals.size();
        int[] left = new int[n], right = new int[n];
        long[] weight = new long[n];
        for (int i = 0; i < n; i++) {
            left[i] = intervals.get(i).get(0);
            right[i] = intervals.get(i).get(1);
            weight[i] = intervals.get(i).get(2);
        }

        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (a, b) -> Integer.compare(left[a], left[b]));

        int[] sortedLefts = new int[n];
        for (int p = 0; p < n; p++) {
            sortedLefts[p] = left[order[p]];
        }

        // nxt[p] = first sorted position whose left endpoint is strictly past r_p;
        // strict because intervals sharing a boundary still overlap
        int[] nxt = new int[n];
        for (int p = 0; p < n; p++) {
            nxt[p] = upperBound(sortedLefts, right[order[p]]);
        }

        // score[p][k] and idx[p][k] = best score and its sorted original indices
        long[][] score = new long[n + 1][5];
        int[][][] idx = new int[n + 1][5][];
        for (int k = 0; k < 5; k++) {
            idx[n][k] = new int[0];
        }

        for (int p = n - 1; p >= 0; p--) {
            idx[p][0] = new int[0];
            for (int k = 1; k <= 4; k++) {
                long bestScore = score[p + 1][k];          // skip this interval
                int[] bestIdx = idx[p + 1][k];

                long candScore = score[nxt[p]][k - 1] + weight[order[p]];
                int[] candIdx = insertSorted(idx[nxt[p]][k - 1], order[p]);

                // higher score wins; ties go to the lexicographically smaller indices
                if (candScore > bestScore
                        || (candScore == bestScore && lexLess(candIdx, bestIdx))) {
                    bestScore = candScore;
                    bestIdx = candIdx;
                }
                score[p][k] = bestScore;
                idx[p][k] = bestIdx;
            }
        }

        return idx[0][4];
    }

    /** First position in a sorted array holding a value 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) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private int[] insertSorted(int[] base, int value) {
        int[] out = new int[base.length + 1];
        int i = 0;
        while (i < base.length && base[i] < value) {
            out[i] = base[i];
            i++;
        }
        out[i] = value;
        while (i < base.length) {
            out[i + 1] = base[i];
            i++;
        }
        return out;
    }

    private boolean lexLess(int[] a, int[] b) {
        int len = Math.min(a.length, b.length);
        for (int i = 0; i < len; i++) {
            if (a[i] != b[i]) {
                return a[i] < b[i];
            }
        }
        return a.length < b.length;
    }
}