We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Events That Can Be Attended II

Difficulty: Hard

Problem Description

You are given an array of events where events[i] = [startDay_i, endDay_i, value_i]. The i-th event starts at startDay_i and ends at endDay_i, and if you attend this event, you will receive a value of value_i. 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.

Key Insights

  • Events can overlap, meaning careful selection is required to maximize value.
  • You can attend at most k events, but attending fewer than k is allowed if events overlap.
  • A dynamic programming approach can be utilized where we track the maximum values up to k events.
  • The problem can be reduced to finding the best non-overlapping events that can be attended.

Space and Time Complexity

Time Complexity: O(n^2 * k) in the worst case due to nested loops for events and k. Space Complexity: O(k) for the DP array.

Solution

To solve the problem, we can use dynamic programming. We will maintain a DP table where dp[i][j] represents the maximum value achievable by attending j events among the first i events. We'll sort the events based on their end day to facilitate the selection of non-overlapping events. For each event, we will consider two options: including the event or excluding it, and update the DP table accordingly.

Code Solutions

def maxValue(events, k):
    events.sort(key=lambda x: x[1])  # Sort events by end day
    n = len(events)
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        start, end, value = events[i - 1]
        for j in range(1, k + 1):
            # Option 1: Do not take the current event
            dp[i][j] = dp[i - 1][j]
            # Option 2: Take the current event
            # Find the last non-overlapping event
            l = 0
            for m in range(i - 1, 0, -1):
                if events[m - 1][1] < start:
                    l = m
                    break
            dp[i][j] = max(dp[i][j], dp[l][j - 1] + value)

    return dp[n][k]
← Back to All Questions