Description
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 * 104intervals[i].length == 3intervals[i] = [li, ri, weighti]1 <= li <= ri <= 1091 <= weighti <= 109
Solutions
Requested memoization to be added to the previous one.
/**
* @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;
};