Maximum Score of Non-overlapping Intervals

Hard

You are given a 2D integer array intervals, where intervals[i] = [l_i, r_i, weight_i]. Interval i starts at position l_i and ends at r_i, and has a weight of weight_i. 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 * 10⁴
intervals[i].length == 3
intervals[i] = [l_i, r_i, weight_i]
1 <= l_i <= r_i <= 10⁹
1 <= weight_i <= 10⁹

Requested memoization to be added to the previous one.

Language: javascript(2026-09-12 08:30 UTC)DONE

CPU Performance40.00%

Memory Performance80.00%

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var maximumWeight = function(intervals) {
    intervals = intervals
        .map((x, i) => [...x, i])
        .sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);

    const n = intervals.length;
    const memo = new Map();

    // First interval whose start > current interval's end
    const getNext = (pos) => {
        let left = pos + 1;
        let right = n;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);

            if (intervals[mid][0] > intervals[pos][1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    };

    const lexSmaller = (a, b) => {
        const len = Math.min(a.length, b.length);

        for (let i = 0; i < len; i++) {
            if (a[i] !== b[i]) {
                return a[i] < b[i];
            }
        }

        return a.length < b.length;
    };

    // Returns:
    // {
    //   score: maximum weight,
    //   indices: original interval indices
    // }
    const dfs = (pos, remaining) => {
        if (pos === n || remaining === 0) {
            return {
                score: 0,
                indices: []
            };
        }

        const key = `${pos},${remaining}`;

        if (memo.has(key)) {
            return memo.get(key);
        }

        // Skip
        const skipped = dfs(pos + 1, remaining);

        // Take
        const next = getNext(pos);
        const takenRest = dfs(next, remaining - 1);

        const taken = {
            score: intervals[pos][2] + takenRest.score,
            indices: [
                intervals[pos][3],
                ...takenRest.indices
            ].sort((a, b) => a - b)
        };

        let result;

        if (taken.score > skipped.score) {
            result = taken;
        } else if (taken.score < skipped.score) {
            result = skipped;
        } else {
            result = lexSmaller(taken.indices, skipped.indices)
                ? taken
                : skipped;
        }

        memo.set(key, result);
        return result;
    };

    return dfs(0, 4).indices;
};

Description

Maximum Score of Non-overlapping Intervals

Solutions

Developer Notes

AI Explanation