Maximum Number of Events That Can Be Attended II LeetCode solution in Java

1
class Solution {
2
  public int maxValue(int[][] events, int k) {
3
    Arrays.sort(events, (e1, e2) -> (e1[0] == e2[0] ? e1[1] - e2[1] : e1[0] - e2[0]));
4
    return maxValue(events, 0, k, 0, new int[k + 1][events.length]);
5
  }
6

7
  private int maxValue(
8
      int[][] events, int index, int remainingEvents, int lastEventEndDay, int[][] dp) {
9
    // Return 0 if no events are left or maximum choice is reached
10
    if (index >= events.length || remainingEvents == 0) return 0;
11

12
    // An Event cannot be picked if the previous event has not completed before current event
13
    if (lastEventEndDay >= events[index][0])
14
      return maxValue(events, index + 1, remainingEvents, lastEventEndDay, dp);
15

16
    // Return the value if the solution is already available
17
    if (dp[remainingEvents][index] != 0) return dp[remainingEvents][index];
18

19
    // There are 2 choices that we can make,
20
    // SKIP this meeting or PICK this meeting
21
    return dp[remainingEvents][index] =
22
        Math.max(
23
            maxValue(events, index + 1, remainingEvents, lastEventEndDay, dp), // skip
24
            maxValue(events, index + 1, remainingEvents - 1, events[index][1], dp)
25
                + events[index][2] // pick
26
            );
27
  }
28
}