Tap here to switch tabs
Problem
Submissions

Problem: Maximum Number of Events That Can Be Attended II

Maximum Number of Events That Can Be Attended II asks you to choose at most k non-overlapping events, each with a start, end, and value, to maximize the total value earned.

Statement

You are given an array events, where each element is a list [startDay_i, endDay_i, value_i] describing an event that starts on day startDay_i, ends on day endDay_i, and provides a value of value_i if you attend it.

You may attend at most k events. Attending an event requires you to be available for every day from startDay_i through endDay_i inclusive, so you cannot attend two events whose date ranges overlap.

Return the maximum total value you can obtain by attending at most k non overlapping events.

Note: You are not required to attend exactly k events.

Constraints:

  • 1≤1 \leq k ≤\leq events.length

  • 1≤1 \leq k ⋅\cdot events.length ≤106\leq 10^6

  • 1≤1 \leq startDay_i ≤\leq endDay_i ≤109\leq 10^9

  • 1≤1 \leq value_i ≤106\leq 10^6

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Number of Events That Can Be Attended II

Maximum Number of Events That Can Be Attended II asks you to choose at most k non-overlapping events, each with a start, end, and value, to maximize the total value earned.

Statement

You are given an array events, where each element is a list [startDay_i, endDay_i, value_i] describing an event that starts on day startDay_i, ends on day endDay_i, and provides a value of value_i if you attend it.

You may attend at most k events. Attending an event requires you to be available for every day from startDay_i through endDay_i inclusive, so you cannot attend two events whose date ranges overlap.

Return the maximum total value you can obtain by attending at most k non overlapping events.

Note: You are not required to attend exactly k events.

Constraints:

  • 1≤1 \leq k ≤\leq events.length

  • 1≤1 \leq k ⋅\cdot events.length ≤106\leq 10^6

  • 1≤1 \leq startDay_i ≤\leq endDay_i ≤109\leq 10^9

  • 1≤1 \leq value_i ≤106\leq 10^6