Maximum score of non overlapping intervals

Array Binary Search Dynamic Programming Sorting

31.1% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_weight(intervals: Vec<Vec<i32>>) -> Vec<i32> {
    let n = intervals.len();
    // Sort by right endpoint; track original index
    let mut sorted: Vec<usize> = (0..n).collect();
    sorted.sort_by(|&a, &b| {
      intervals[a][1].cmp(&intervals[b][1])
        .then(intervals[a][0].cmp(&intervals[b][0]))
    });
    // prev[i] = last sorted index j where r[j] < l[sorted[i]]
    let prev: Vec<i32> = (0..n).map(|i| {
      let l = intervals[sorted[i]][0];
      let p = sorted[..i].partition_point(|&j| intervals[j][1] < l);
      p as i32 - 1
    }).collect();
    // dp[j][i] = (max_score, lex_min_indices) using exactly j intervals, last = sorted[i]
    // better(a, b): a has higher score, or same score with strictly smaller index array
    let better = |a: &(i64, Vec<i32>), b: &(i64, Vec<i32>)| -> bool {
      a.0 > b.0 || (a.0 == b.0 && a.1 < b.1)
    };
    const K: usize = 4;
    let neg = (i64::MIN / 2, vec![-1i32]);
    let mut dp: Vec<Vec<(i64, Vec<i32>)>> = vec![vec![neg.clone(); n]; K + 1];
    let mut best: Vec<Vec<(i64, Vec<i32>)>> = vec![vec![neg.clone(); n + 1]; K + 1];
    for j in 0..=K { best[j][0] = (0i64, vec![]); }

    for i in 0..n {
      let orig_i = sorted[i] as i32;
      let w = intervals[sorted[i]][2] as i64;
      for j in 1..=K {
        // Use interval sorted[i] as the j-th interval
        let prev_best = if prev[i] >= 0 {
          &best[j-1][(prev[i] + 1) as usize]
        } else {
          &best[j-1][0]
        };
        if prev_best.0 < 0 && j > 1 { continue; }
        let new_score = prev_best.0 + w;
        let mut new_path = prev_best.1.clone();
        // Insert orig_i in sorted order
        let ins = new_path.partition_point(|&x| x < orig_i);
        new_path.insert(ins, orig_i);
        let cand = (new_score, new_path);
        if better(&cand, &dp[j][i]) { dp[j][i] = cand; }
      }
      // Update best[j][i+1] = better of best[j][i] and dp[j][i]
      for j in 0..=K {
        let prev_b = best[j][i].clone();
        let cur_d = dp[j][i].clone();
        best[j][i + 1] = if better(&cur_d, &prev_b) { cur_d } else { prev_b };
      }
    }
    // Find overall best
    let mut ans = (i64::MIN, vec![]);
    for j in 1..=K {
      let b = &best[j][n];
      if b.0 > ans.0 || (b.0 == ans.0 && b.1 < ans.1) {
        ans = b.clone();
      }
    }
    ans.1
  }
}