Maximum Number of Events That Can Be Attended II

Problem Statement

In this problem, you are provided with an array named events, where each event is described by three characteristics enclosed within subarrays: the start day (startDayi), the end day (endDayi), and a value (valuei) accrued from attending the event. This array represents various events you could potentially attend. Additionally, an integer k specifies the maximum number of events you can participate in.

One critical rule to follow when choosing events is that event attendance schedules cannot overlap. Specifically, if you attend an event from startDayi to endDayi, those days are wholly occupied, and you cannot start another event any day within that range. Put another way, there must be at least a one-day gap between the end of one event and the start of another to attend both.

The goal is to select up to k events in such a manner that the sum of the values (valuei) of the events attended is maximized.

Examples

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 <= 106
• 1 <= startDayi <= endDayi <= 109
• 1 <= valuei <= 106

Approach and Intuition

Given the problem's constraints and structure, the naive approach of trying every combination of events is impractical due to the potential size of events and k. Thus, a more nuanced strategy is needed, such as dynamic programming or greedy algorithms with smart sorting. However, here is a simplified thought process to approach the problem:

1. Sort Events: First, sort the events based on their start days or end days. Sorting events can help in quickly identifying non-overlapping events.

2. Dynamic Programming Setup:

   • Define an array dp[j] where j ranges from 0 to k. dp[j] could represent the maximum sum of values from attending up to j events.
   • Initialize dp[0] to 0 because attending zero events yields a value sum of 0.

3. Event Selection: Utilize nested loops where the outer loop iterates through events and the inner loop manages the count of events up to k:

   • For each event, check combinations of previously selected events that do not overlap with the current event.
   • Update the DP array by considering whether including the current event increases the maximum value sum for any count of up to k events.

4. Optimizing for Non-overlapping Events:

   • After adding a new event, examine the start time of this event against the end times of previous events to ensure there's no overlap.

5. Result Extraction: By the end of iterations, dp[k] will contain the maximum value sum for attending up to k events.

By following the above approach and carefully implementing checks for overlaps and value calculations, the solution not only adheres to the constraints but also ensures optimal selection of events for maximum value. This process efficiently narrows down the options by logically sequencing the decision-making and storing intermediate results, thus reducing redundant calculations.

Solutions

class Solution {
    int[][] memoization;
    public int maximumValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int length = events.length;
        memoization = new int[k + 1][length];
        for (int[] row : memoization) {
            Arrays.fill(row, -1);
        }
        return search(0, 0, -1, events, k);
    }
    
    private int search(int currentIndex, int numberOfEvents, int lastEndTime, int[][] events, int maxEvents) {
        if (currentIndex == events.length || numberOfEvents == maxEvents) {
            return 0;
        }
        
        if (lastEndTime >= events[currentIndex][0]) {
            return search(currentIndex + 1, numberOfEvents, lastEndTime, events, maxEvents);
        }
        
        if (memoization[numberOfEvents][currentIndex] != -1) {
            return memoization[numberOfEvents][currentIndex];
        }
        
        int value = Math.max(search(currentIndex + 1, numberOfEvents, lastEndTime, events, maxEvents),
                           search(currentIndex + 1, numberOfEvents + 1, events[currentIndex][1], events, maxEvents) + events[currentIndex][2]);
        memoization[numberOfEvents][currentIndex] = value;
        return value;
    }
}