0

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?

1 Answer 1

2

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;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.