Leetcode Problem 1751. Maximum Number of Events That Can Be Attended II

1751. Maximum Number of Events That Can Be Attended II

Leetcode Solutions

Top-down Dynamic Programming + Binary Search

  1. Sort events by start time.
  2. Initialize a 2D array dp for memoization.
  3. Define the recursive function dfs(cur_index, count).
    • If the result for the current state is already computed, return it from dp.
    • If count is 0 or cur_index is out of bounds, return 0.
    • Calculate the value of skipping the current event: skip_value = dfs(cur_index + 1, count).
    • Use binary search to find the index next_index of the nearest event that can be attended after cur_index.
    • Calculate the value of attending the current event: attend_value = events[cur_index][2] + dfs(next_index, count - 1).
    • Store the maximum of skip_value and attend_value in dp[count][cur_index].
  4. Return the result of dfs(0, k).
UML Thumbnail

Bottom-up Dynamic Programming + Binary Search

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...