1751. Maximum Number of Events That Can Be Attended II

Problem

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.**

  Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

  Constraints:

• 1 <= k <= events.length

• 1 <= k * events.length <= 10^6

• 1 <= startDayi <= endDayi <= 10^9

• 1 <= valuei <= 10^6

Solution

import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;

class Solution {
    public int maxValue(int[][] events, int k) {
        if (k == 1) {
            Optional<int[]> value = Arrays.stream(events).max(Comparator.comparingInt(e -> e[2]));
            if (value.isPresent()) {
                return value.get()[2];
            } else {
                throw new NullPointerException();
            }
        }

        int n = events.length;
        Arrays.sort(events, Comparator.comparingInt(a -> a[0]));

        int[][] memo = new int[n][k + 1];

        return dfs(events, 0, k, memo);
    }

    private int dfs(int[][] events, int i, int k, int[][] memo) {
        if (k == 0 || i >= events.length) {
            return 0;
        }
        if (memo[i][k] > 0) {
            return memo[i][k];
        }

        int idx = binarySearch(events, events[i][1] + 1, i + 1);
        int use = events[i][2] + dfs(events, idx, k - 1, memo);

        int notUse = dfs(events, i + 1, k, memo);

        int res = Math.max(use, notUse);
        memo[i][k] = res;

        return res;
    }

    private int binarySearch(int[][] events, int i, int st) {

        if (st >= events.length) {
            return st;
        }

        int end = events.length - 1;
        while (st < end) {
            int mid = st + (end - st) / 2;
            if (events[mid][0] < i) {
                st = mid + 1;
            } else {
                end = mid;
            }
        }

        return events[st][0] >= i ? st : st + 1;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).