Maximum Score of Non-overlapping Intervals
HardUpdated: Aug 8, 2025
Practice on:
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 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.
Examples
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^4intervals[i].length == 3intervals[i] = [li, ri, weighti]1 <= li <= ri <= 10^91 <= weighti <= 10^9
Solution
Method 1 – Dynamic Programming with Binary Search
Intuition
This problem can be solved using a 0/1 knapsack approach since we need to choose at most 4 intervals. The key insight is to sort intervals by their start time and use dynamic programming to track the maximum weight achievable when selecting exactly j intervals ending at position i. For each interval, we can either skip it or take it (if it doesn't overlap with previously selected intervals).
Approach
- Sort intervals by start time
l, and append original indices to track the answer. - Precompute the next non-overlapping interval for each interval using binary search to find the first interval that starts after the current interval ends.
- Use DP where
dp[i][j]represents the maximum weight when considering intervals from positionionwards and selecting exactlyjintervals. - Also track
choose[i][j]to store the indices of selected intervals for reconstruction. - For each interval, apply 0/1 knapsack logic: either skip the current interval or take it (and jump to the next non-overlapping interval).
- When weights are equal, choose the lexicographically smaller index combination.
- Process DP backwards from the last interval to the first.
Code
C++
class Solution {
public:
vector<int> maximumWeight(vector<vector<int>>& intervals) {
int n = intervals.size();
// Add original indices to intervals
for (int i = 0; i < n; ++i) {
intervals[i].push_back(i);
}
// Sort by start time
sort(intervals.begin(), intervals.end());
// Precompute next non-overlapping interval for each interval
vector<int> nxt(n);
for (int i = 0; i < n; ++i) {
int end = intervals[i][1];
int l = 0, r = n;
while (l < r) {
int m = (l + r) / 2;
if (intervals[m][0] > end) r = m;
else l = m + 1;
}
nxt[i] = l;
}
const int INF = 1e9;
vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0));
vector<vector<array<int, 4>>> choose(n + 1, vector<array<int, 4>>(5, {INF, INF, INF, INF}));
// DP backwards
for (int i = n - 1; i >= 0; --i) {
for (int c = 3; c >= 0; --c) {
// Option 1: Skip current interval
int64_t skip = dp[i + 1][c];
array<int, 4> svec = choose[i + 1][c];
// Option 2: Take current interval
int64_t take = dp[nxt[i]][c + 1] + intervals[i][2];
array<int, 4> tvec = choose[nxt[i]][c + 1];
tvec[3] = intervals[i][3]; // Add current interval's original index
sort(tvec.begin(), tvec.end());
// Choose better option (or lexicographically smaller if equal)
if (skip > take || (skip == take && svec < tvec)) {
dp[i][c] = skip;
choose[i][c] = svec;
} else {
dp[i][c] = take;
choose[i][c] = tvec;
}
}
}
// Extract result
vector<int> ans;
for (int id : choose[0][0]) {
if (id != INF) ans.push_back(id);
}
return ans;
}
};
Go
import "sort"
func maximumWeight(intervals [][]int) []int {
n := len(intervals)
// Add original indices to intervals
for i := 0; i < n; i++ {
intervals[i] = append(intervals[i], i)
}
// Sort by start time
sort.Slice(intervals, func(i, j int) bool {
if intervals[i][0] != intervals[j][0] {
return intervals[i][0] < intervals[j][0]
}
if intervals[i][1] != intervals[j][1] {
return intervals[i][1] < intervals[j][1]
}
return intervals[i][2] < intervals[j][2]
})
// Precompute next non-overlapping interval for each interval
nxt := make([]int, n)
for i := 0; i < n; i++ {
end := intervals[i][1]
l, r := 0, n
for l < r {
m := (l + r) / 2
if intervals[m][0] > end {
r = m
} else {
l = m + 1
}
}
nxt[i] = l
}
const INF = 1e9
dp := make([][]int64, n+1)
choose := make([][][4]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int64, 5)
choose[i] = make([][4]int, 5)
for j := 0; j < 5; j++ {
choose[i][j] = [4]int{INF, INF, INF, INF}
}
}
// DP backwards
for i := n - 1; i >= 0; i-- {
for c := 3; c >= 0; c-- {
// Option 1: Skip current interval
skip := dp[i+1][c]
svec := choose[i+1][c]
// Option 2: Take current interval
take := dp[nxt[i]][c+1] + int64(intervals[i][2])
tvec := choose[nxt[i]][c+1]
tvec[3] = intervals[i][3] // Add current interval's original index
sort.Ints(tvec[:])
// Choose better option (or lexicographically smaller if equal)
if skip > take || (skip == take && less(svec, tvec)) {
dp[i][c] = skip
choose[i][c] = svec
} else {
dp[i][c] = take
choose[i][c] = tvec
}
}
}
// Extract result
var ans []int
for _, id := range choose[0][0] {
if id != INF {
ans = append(ans, id)
}
}
return ans
}
func less(a, b [4]int) bool {
for i := 0; i < 4; i++ {
if a[i] != b[i] {
return a[i] < b[i]
}
}
return false
}
Java
import java.util.*;
class Solution {
public int[] maximumWeight(int[][] intervals) {
int n = intervals.length;
// Add original indices to intervals
int[][] newIntervals = new int[n][4];
for (int i = 0; i < n; i++) {
newIntervals[i][0] = intervals[i][0]; // start
newIntervals[i][1] = intervals[i][1]; // end
newIntervals[i][2] = intervals[i][2]; // weight
newIntervals[i][3] = i; // original index
}
// Sort by start time
Arrays.sort(newIntervals, (a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
return Integer.compare(a[2], b[2]);
});
// Precompute next non-overlapping interval for each interval
int[] nxt = new int[n];
for (int i = 0; i < n; i++) {
int end = newIntervals[i][1];
int l = 0, r = n;
while (l < r) {
int m = (l + r) / 2;
if (newIntervals[m][0] > end) {
r = m;
} else {
l = m + 1;
}
}
nxt[i] = l;
}
final int INF = (int) 1e9;
long[][] dp = new long[n + 1][5];
int[][][] choose = new int[n + 1][5][4];
// Initialize choose arrays with INF
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 5; j++) {
Arrays.fill(choose[i][j], INF);
}
}
// DP backwards
for (int i = n - 1; i >= 0; i--) {
for (int c = 3; c >= 0; c--) {
// Option 1: Skip current interval
long skip = dp[i + 1][c];
int[] svec = choose[i + 1][c].clone();
// Option 2: Take current interval
long take = dp[nxt[i]][c + 1] + newIntervals[i][2];
int[] tvec = choose[nxt[i]][c + 1].clone();
tvec[3] = newIntervals[i][3]; // Add current interval's original index
Arrays.sort(tvec);
// Choose better option (or lexicographically smaller if equal)
if (skip > take || (skip == take && compare(svec, tvec) < 0)) {
dp[i][c] = skip;
choose[i][c] = svec;
} else {
dp[i][c] = take;
choose[i][c] = tvec;
}
}
}
// Extract result
List<Integer> result = new ArrayList<>();
for (int id : choose[0][0]) {
if (id != INF) {
result.add(id);
}
}
return result.stream().mapToInt(i -> i).toArray();
}
private int compare(int[] a, int[] b) {
for (int i = 0; i < 4; i++) {
if (a[i] != b[i]) {
return Integer.compare(a[i], b[i]);
}
}
return 0;
}
}
Kotlin
class Solution {
fun maximumWeight(intervals: Array<IntArray>): IntArray {
val n = intervals.size
// Add original indices to intervals
val newIntervals = Array(n) { i ->
intArrayOf(intervals[i][0], intervals[i][1], intervals[i][2], i)
}
// Sort by start time
newIntervals.sortWith { a, b ->
when {
a[0] != b[0] -> a[0].compareTo(b[0])
a[1] != b[1] -> a[1].compareTo(b[1])
else -> a[2].compareTo(b[2])
}
}
// Precompute next non-overlapping interval for each interval
val nxt = IntArray(n)
for (i in 0 until n) {
val end = newIntervals[i][1]
var l = 0
var r = n
while (l < r) {
val m = (l + r) / 2
if (newIntervals[m][0] > end) {
r = m
} else {
l = m + 1
}
}
nxt[i] = l
}
val INF = 1_000_000_000
val dp = Array(n + 1) { LongArray(5) }
val choose = Array(n + 1) { Array(5) { IntArray(4) { INF } } }
// DP backwards
for (i in n - 1 downTo 0) {
for (c in 3 downTo 0) {
// Option 1: Skip current interval
val skip = dp[i + 1][c]
val svec = choose[i + 1][c].clone()
// Option 2: Take current interval
val take = dp[nxt[i]][c + 1] + newIntervals[i][2]
val tvec = choose[nxt[i]][c + 1].clone()
tvec[3] = newIntervals[i][3] // Add current interval's original index
tvec.sort()
// Choose better option (or lexicographically smaller if equal)
if (skip > take || (skip == take && compare(svec, tvec) < 0)) {
dp[i][c] = skip
choose[i][c] = svec
} else {
dp[i][c] = take
choose[i][c] = tvec
}
}
}
// Extract result
return choose[0][0].filter { it != INF }.toIntArray()
}
private fun compare(a: IntArray, b: IntArray): Int {
for (i in 0 until 4) {
if (a[i] != b[i]) {
return a[i].compareTo(b[i])
}
}
return 0
}
}
Python
class Solution:
def maxWeight(self, intervals: list[list[int]]) -> list[int]:
n = len(intervals)
arr = sorted([(r, l, w, i) for i, (l, r, w) in enumerate(intervals)])
ends = [r for r, l, w, i in arr]
dp = [[0]*5 for _ in range(n+1)]
idx = [[[] for _ in range(5)] for _ in range(n+1)]
for i in range(1, n+1):
for k in range(1, 5):
l = bisect.bisect_left(ends, arr[i-1][1])
if dp[i-1][k] > dp[l][k-1] + arr[i-1][2]:
dp[i][k] = dp[i-1][k]
idx[i][k] = idx[i-1][k][:]
elif dp[i-1][k] < dp[l][k-1] + arr[i-1][2]:
dp[i][k] = dp[l][k-1] + arr[i-1][2]
idx[i][k] = idx[l][k-1][:] + [arr[i-1][3]]
else:
a = idx[i-1][k][:]
b = idx[l][k-1][:] + [arr[i-1][3]]
if a < b:
dp[i][k] = dp[i-1][k]
idx[i][k] = a
else:
dp[i][k] = dp[l][k-1] + arr[i-1][2]
idx[i][k] = b
best = 0
ans = []
for k in range(1, 5):
if dp[n][k] > best:
best = dp[n][k]
ans = idx[n][k][:]
elif dp[n][k] == best and (not ans or idx[n][k] < ans):
ans = idx[n][k][:]
ans.sort()
##### Rust
```rust
impl Solution {
pub fn maximum_weight(mut intervals: Vec<Vec<i32>>) -> Vec<i32> {
let n = intervals.len();
// Add original indices to intervals
for i in 0..n {
intervals[i].push(i as i32);
}
// Sort by start time
intervals.sort_by(|a, b| {
a[0].cmp(&b[0])
.then_with(|| a[1].cmp(&b[1]))
.then_with(|| a[2].cmp(&b[2]))
});
// Precompute next non-overlapping interval for each interval
let mut nxt = vec![0; n];
for i in 0..n {
let end = intervals[i][1];
let mut l = 0;
let mut r = n;
while l < r {
let m = (l + r) / 2;
if intervals[m][0] > end {
r = m;
} else {
l = m + 1;
}
}
nxt[i] = l;
}
const INF: i32 = 1_000_000_000;
let mut dp = vec![vec![0i64; 5]; n + 1];
let mut choose = vec![vec![[INF; 4]; 5]; n + 1];
// DP backwards
for i in (0..n).rev() {
for c in (0..=3).rev() {
// Option 1: Skip current interval
let skip = dp[i + 1][c];
let svec = choose[i + 1][c];
// Option 2: Take current interval
let take = dp[nxt[i]][c + 1] + intervals[i][2] as i64;
let mut tvec = choose[nxt[i]][c + 1];
tvec[3] = intervals[i][3]; // Add current interval's original index
tvec.sort();
// Choose better option (or lexicographically smaller if equal)
if skip > take || (skip == take && svec < tvec) {
dp[i][c] = skip;
choose[i][c] = svec;
} else {
dp[i][c] = take;
choose[i][c] = tvec;
}
}
}
// Extract result
choose[0][0]
.iter()
.filter(|&&id| id != INF)
.copied()
.collect()
}
}
TypeScript
function maximumWeight(intervals: number[][]): number[] {
const n = intervals.length;
// Add original indices to intervals
const newIntervals: number[][] = intervals.map((interval, i) => [...interval, i]);
// Sort by start time
newIntervals.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
if (a[1] !== b[1]) return a[1] - b[1];
return a[2] - b[2];
});
// Precompute next non-overlapping interval for each interval
const nxt: number[] = new Array(n);
for (let i = 0; i < n; i++) {
const end = newIntervals[i][1];
let l = 0, r = n;
while (l < r) {
const m = Math.floor((l + r) / 2);
if (newIntervals[m][0] > end) {
r = m;
} else {
l = m + 1;
}
}
nxt[i] = l;
}
const INF = 1e9;
const dp: number[][] = Array(n + 1).fill(null).map(() => Array(5).fill(0));
const choose: number[][][] = Array(n + 1).fill(null).map(() =>
Array(5).fill(null).map(() => Array(4).fill(INF))
);
// DP backwards
for (let i = n - 1; i >= 0; i--) {
for (let c = 3; c >= 0; c--) {
// Option 1: Skip current interval
const skip = dp[i + 1][c];
const svec = [...choose[i + 1][c]];
// Option 2: Take current interval
const take = dp[nxt[i]][c + 1] + newIntervals[i][2];
const tvec = [...choose[nxt[i]][c + 1]];
tvec[3] = newIntervals[i][3]; // Add current interval's original index
tvec.sort((a, b) => a - b);
// Choose better option (or lexicographically smaller if equal)
if (skip > take || (skip === take && compare(svec, tvec) < 0)) {
dp[i][c] = skip;
choose[i][c] = svec;
} else {
dp[i][c] = take;
choose[i][c] = tvec;
}
}
}
// Extract result
return choose[0][0].filter(id => id !== INF);
}
function compare(a: number[], b: number[]): number {
for (let i = 0; i < 4; i++) {
if (a[i] !== b[i]) {
return a[i] - b[i];
}
}
return 0;
}
Complexity
- ⏰ Time complexity:
O(n log n), wherenis the number of intervals. The sorting takesO(n log n)and the DP with binary search preprocessing takesO(n log n)total time. - 🧺 Space complexity:
O(n), for the DP tables and index tracking arrays.ms