Untitled

import java.util.*;

class Solution {
    public int maxValue(int[][] events, int k) {
        // Sort events by start day
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
        int n = events.length;

        // Precompute nextIndices for each event
        int[] nextIndices = new int[n];
        for (int i = 0; i < n; i++) {
            nextIndices[i] = findNextEvent(events, events[i][1]);
        }

        // Memoization array
        int[][] memo = new int[n][k + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        // Recursive function with memoization
        return dp(0, k, events, nextIndices, memo);
    }

    private int dp(int index, int remainingEvents, int[][] events, int[] nextIndices, int[][] memo) {
        if (index >= events.length || remainingEvents == 0) {
            return 0;
        }
        if (memo[index][remainingEvents] != -1) {
            return memo[index][remainingEvents];
        }

        // Option 1: Do not attend the current event
        int option1 = dp(index + 1, remainingEvents, events, nextIndices, memo);

        // Option 2: Attend the current event
        int nextEventIndex = nextIndices[index];
        int option2 = events[index][2] + dp(nextEventIndex, remainingEvents - 1, events, nextIndices, memo);

        // Choose the maximum of the two options
        memo[index][remainingEvents] = Math.max(option1, option2);
        return memo[index][remainingEvents];
    }

    private int findNextEvent(int[][] events, int currentEnd) {
        int left = 0, right = events.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (events[mid][0] > currentEnd) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] events1 = {{1, 2, 4}, {3, 4, 3}, {2, 3, 1}};
        int k1 = 2;
        System.out.println(solution.maxValue(events1, k1)); // Output: 7

        int[][] events2 = {{1, 2, 4}, {3, 4, 3}, {2, 3, 10}};
        int k2 = 2;
        System.out.println(solution.maxValue(events2, k2)); // Output: 10

        int[][] events3 = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}};
        int k3 = 3;
        System.out.println(solution.maxValue(events3, k3)); // Output: 9
    }
}