Maximum number of events that can be attended ii

Array Binary Search Dynamic Programming Sorting

63.6% acceptance

Feb 25, 2026

2546

You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this event, you will receive a value of valuei. You are also given an integer k which represents the maximum number of events you can attend. You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day. Return the maximum sum of values that you can receive by attending events.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
    events.sort_by_key(|e| e[1]);
    let n = events.len();
    let k = k as usize;
    // dp[j][i] = max value attending exactly j events among first i+1
    // But use 2D array dp[k+1][n+1]
    let mut dp = vec![vec![0i32; n + 1]; k + 1];
    for j in 1..=k {
      for i in 0..n {
        // Don't attend event i
        dp[j][i + 1] = dp[j][i];
        // Attend event i: find last event ending before events[i][0]
        let start = events[i][0];
        let val = events[i][2];
        // Binary search for last event with end < start
        let pos = events[..i].partition_point(|e| e[1] < start);
        dp[j][i + 1] = dp[j][i + 1].max(dp[j - 1][pos] + val);
      }
    }
    dp[k][n]
  }
}