How should I apply dynamic programming on the following problem

Question

I have an array of events where events[i] = [startDay_i, endDay_i, value_i]. The ith event starts at startDay_i and ends at endDay_i, Attending the ith event, I will receive value_i. Also given an integer k which represents the maximum number of events I can attend.

It's required to attend the event only once at a time, and not allowed to attend two events with overlapping time.

I want to calculate the maximum sum of values by attending events.

I tried to use dynamic programming to solve this: let f[i] be the maximum sum within i days, and it depends on every f[j] where j < i, and I have to iterate every j and find out the events that endDay is before i. This is a O(n^3) approach. Any way I can do it better?

Answer 1

This is a O(n^3) approach

The time complexity has to do with k as well. The DP should give you a O(nk) instead.

Similar with a knapsack problem, you can use a recursive way with memorization to implement the DP.

• Sort the event by startDay (by endDay if startDay equals).
• Memorize the maximum value you can get by attending x events prior to time t.
• For each depth of recursion, you can either attend the current event or skip, so the recursive logic looks like

int solve(int x, int t, int count)
{
    // some edge cases processing
    
    if (cache has the value for x and t)
    {
         return cache.get(x, t);
    }
        
    // skip current event
    int max = solve(x+1, t, count);
    if (events[cur][0] > t) // make sure no overlapping on the events
    {
        max = max(max, solve(x+1, events[x][1], count+1) + events[x][2]);
    }
    
    // Add max value to the cache with x, t as its key

    return max;
}