3414 LeetCode problem solution
LeetCode problem link: 3414. Maximum Score of Non-overlapping Intervals
LeetCode 3414 problem description
This is Hard level 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 smallest1 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
LeetCode 3414 problem: solution explanation
In this case we use the Weighted Interval Scheduling pattern with Dynamic Programming and Binary Search patterns.
First, we sort all intervals by their right endpoint while keeping their original indices.
For each interval, we use binary search to find the last interval whose right endpoint is strictly smaller than the current left endpoint.
The strict comparison is important because intervals that share a boundary are considered overlapping.
For each interval, the DP chooses between skipping it or taking it together with the best compatible previous intervals.
Since we can select at most four intervals, each interval only needs four DP states.
Each state stores the maximum total score and up to four original indices of the selected intervals.
When two states have the same score, we compare their indices and keep the lexicographically smaller sequence.
Using a fixed array<int, 4> instead of a dynamic vector reduces memory allocations and unnecessary sorting overhead.
The final complexity is O(n log n) time due to sorting and binary searches, with O(n) space for the DP and preprocessing arrays.
Time complexity: O(n log n)
Space complexity: O(n)
LeetCode 3414 C++ solution
class Solution {
public:
struct State
{
long long score = 0;
array<int, 4> idx = {};
int size = 0;
};
bool isBetter(const State& a, const State& b)
{
if(a.score != b.score) return a.score > b.score;
for(int i = 0; i < min(a.size, b.size); i++)
if(a.idx[i] != b.idx[i]) return a.idx[i] < b.idx[i];
return a.size < b.size;
}
State addIndex(State state, int index)
{
int pos = state.size;
while(pos > 0 && state.idx[pos - 1] > index)
{
state.idx[pos] = state.idx[pos - 1];
pos--;
}
state.idx[pos] = index;
state.size++;
return state;
}
vector<int> maximumWeight(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<array<long long, 4>> arr(n);
for(int i = 0; i < n; i++)
{
arr[i] =
{
intervals[i][0],
intervals[i][1],
intervals[i][2],
i
};
}
sort(arr.begin(), arr.end(), [](const auto& a, const auto& b) { return a[1] < b[1]; });
vector<long long> ends(n);
for(int i = 0; i < n; i++) ends[i] = arr[i][1];
vector<int> prev(n);
for(int i = 0; i < n; i++)
prev[i] = lower_bound(ends.begin(), ends.begin() + i, arr[i][0]) - ends.begin() - 1;
vector<array<State, 5>> dp(n + 1);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= 4; j++)
{
State skip = dp[i - 1][j];
State take = dp[prev[i - 1] + 1][j - 1];
take.score += arr[i - 1][2];
take = addIndex(take, arr[i - 1][3]);
dp[i][j] = isBetter(take, skip) ? take : skip;
}
}
State& ans = dp[n][4];
return vector<int>(ans.idx.begin(), ans.idx.begin() + ans.size);
}
};LeetCode 3414 Java solution
import java.util.*;
class Solution {
static class State {
long score;
int[] idx = new int[4];
int size;
}
private boolean isBetter(State a, State b) {
if(a.score != b.score) return a.score > b.score;
for(int i = 0; i < Math.min(a.size, b.size); i++) {
if(a.idx[i] != b.idx[i]) return a.idx[i] < b.idx[i];
}
return a.size < b.size;
}
private State copyState(State state) {
State copy = new State();
copy.score = state.score;
copy.size = state.size;
copy.idx = state.idx.clone();
return copy;
}
private State addIndex(State state, int index) {
State res = copyState(state);
int pos = res.size;
while (pos > 0 && res.idx[pos - 1] > index) {
res.idx[pos] = res.idx[pos - 1];
pos--;
}
res.idx[pos] = index;
res.size++;
return res;
}
public int[] maximumWeight(List<List<Integer>> intervals) {
int n = intervals.size();
long[][] arr = new long[n][4];
for(int i = 0; i < n; i++) {
arr[i][0] = intervals.get(i).get(0);
arr[i][1] = intervals.get(i).get(1);
arr[i][2] = intervals.get(i).get(2);
arr[i][3] = i;
}
Arrays.sort(arr, Comparator.comparingLong(a -> a[1]));
long[] ends = new long[n];
for(int i = 0; i < n; i++) ends[i] = arr[i][1];
int[] prev = new int[n];
for(int i = 0; i < n; i++) {
int left = 0;
int right = i;
while(left < right) {
int mid = left + (right - left) / 2;
if (ends[mid] < arr[i][0]) {
left = mid + 1;
} else {
right = mid;
}
}
prev[i] = left - 1;
}
State[][] dp = new State[n + 1][5];
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= 4; j++) {
dp[i][j] = new State();
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 4; j++) {
State skip = dp[i - 1][j];
State take = addIndex(dp[prev[i - 1] + 1][j - 1], (int) arr[i - 1][3]);
take.score += arr[i - 1][2];
dp[i][j] = isBetter(take, skip) ? take : copyState(skip);
}
}
State ans = dp[n][4];
return Arrays.copyOf(ans.idx, ans.size);
}
}LeetCode 3414 JavaScript solution
var maximumWeight = function(intervals) {
const n = intervals.length;
const arr = intervals.map((interval, i) => [
interval[0],
interval[1],
interval[2],
i
]);
arr.sort((a, b) => a[1] - b[1]);
const ends = arr.map(x => x[1]);
const prev = new Array(n);
for(let i = 0; i < n; i++) {
let left = 0;
let right = i;
while(left < right) {
const mid = Math.floor((left + right) / 2);
if(ends[mid] < arr[i][0]) {
left = mid + 1;
} else {
right = mid;
}
}
prev[i] = left - 1;
}
const isBetter = (a, b) => {
if(a.score !== b.score) return a.score > b.score;
const len = Math.min(a.idx.length, b.idx.length);
for(let i = 0; i < len; i++) {
if (a.idx[i] !== b.idx[i]) return a.idx[i] < b.idx[i];
}
return a.idx.length < b.idx.length;
};
const addIndex = (state, index) => {
const idx = [...state.idx];
let pos = idx.length;
idx.push(index);
while(pos > 0 && idx[pos - 1] > index) {
idx[pos] = idx[pos - 1];
pos--;
}
idx[pos] = index;
return {
score: state.score,
idx
};
};
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: 5 }, () => ({
score: 0,
idx: []
}))
);
for(let i = 1; i <= n; i++) {
for(let j = 1; j <= 4; j++) {
const skip = dp[i - 1][j];
const take = addIndex(dp[prev[i - 1] + 1][j - 1], arr[i - 1][3]);
take.score += arr[i - 1][2];
dp[i][j] = isBetter(take, skip) ? take : skip;
}
}
return dp[n][4].idx;
};LeetCode 3414 TypeScript solution
type State = {
score: number;
idx: number[];
};
function maximumWeight(intervals: number[][]): number[] {
const n = intervals.length;
const arr: number[][] = intervals.map((interval, i) => [
interval[0],
interval[1],
interval[2],
i
]);
arr.sort((a, b) => a[1] - b[1]);
const ends: number[] = arr.map(x => x[1]);
const prev: number[] = new Array(n);
for(let i = 0; i < n; i++) {
let left = 0;
let right = i;
while(left < right) {
const mid = Math.floor((left + right) / 2);
if(ends[mid] < arr[i][0]) {
left = mid + 1;
} else {
right = mid;
}
}
prev[i] = left - 1;
}
const isBetter = (a: State, b: State): boolean => {
if(a.score !== b.score) return a.score > b.score;
const len = Math.min(a.idx.length, b.idx.length);
for(let i = 0; i < len; i++)
if(a.idx[i] !== b.idx[i]) return a.idx[i] < b.idx[i];
return a.idx.length < b.idx.length;
};
const addIndex = (state: State, index: number): State => {
const idx = [...state.idx];
let pos = idx.length;
idx.push(index);
while(pos > 0 && idx[pos - 1] > index) {
idx[pos] = idx[pos - 1];
pos--;
}
idx[pos] = index;
return {
score: state.score,
idx
};
};
const dp: State[][] = Array.from({ length: n + 1 }, () =>
Array.from({ length: 5 }, () => ({score: 0, idx: []})));
for(let i = 1; i <= n; i++) {
for(let j = 1; j <= 4; j++) {
const skip = dp[i - 1][j];
const take = addIndex(dp[prev[i - 1] + 1][j - 1], arr[i - 1][3]);
take.score += arr[i - 1][2];
dp[i][j] = isBetter(take, skip) ? take : skip;
}
}
return dp[n][4].idx;
}LeetCode 3414 Python solution
class Solution:
def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
n = len(intervals)
arr = [
[l, r, w, i]
for i, (l, r, w) in enumerate(intervals)
]
arr.sort(key=lambda x: x[1])
ends = [x[1] for x in arr]
prev = [0] * n
for i in range(n):
left = 0
right = i
while left < right:
mid = (left + right) // 2
if ends[mid] < arr[i][0]:
left = mid + 1
else:
right = mid
prev[i] = left - 1
def is_better(a, b):
if a[0] != b[0]:
return a[0] > b[0]
return a[1] < b[1]
def add_index(state, index):
score, indices = state
indices = indices[:]
pos = len(indices)
indices.append(index)
while pos > 0 and indices[pos - 1] > index:
indices[pos] = indices[pos - 1]
pos -= 1
indices[pos] = index
return score, indices
dp = [
[(0, []) for _ in range(5)]
for _ in range(n + 1)
]
for i in range(1, n + 1):
for j in range(1, 5):
skip = dp[i - 1][j]
score, indices = add_index(dp[prev[i - 1] + 1][j - 1], arr[i - 1][3])
take = (score + arr[i - 1][2], indices)
dp[i][j] = take if is_better(take, skip) else skip
return dp[n][4][1]