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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Events That Can Be Attended II

Number: 1851

Difficulty: Hard

Paid? No

Companies: Microsoft, Amazon, Oracle, General Electric

Problem Description

You are given an array of events where each event is represented as [startDay, endDay, value]. An event can be attended if you commit to all its days (from startDay to endDay inclusively) and you cannot attend overlapping events (note that if an event ends on day d, another event cannot start on day d). Given a maximum of k events to attend, return the maximum sum of values you can achieve.

Key Insights

  • Sort the events by their start day to streamline the search for the next non-overlapping event.
  • Use dynamic programming (DP) to decide whether to attend or skip an event.
  • Employ binary search on the sorted event list to quickly find the next event that starts after the current event's end day.
  • Use memoization or iterative DP to calculate the maximum value for each event index with a given number of events left.

Space and Time Complexity

Time Complexity: O(n * k * log n), where n is the number of events. Sorting takes O(n log n) and each DP state uses a binary search over n events. Space Complexity: O(n * k) if using memoization to store intermediate DP results.

Solution

We solve the problem by first sorting the events by their start day. For each event, we decide whether to attend the event (if we have remaining events to attend) or skip it. Attending the event awards its value and then we must jump to the next event that starts after the current event’s end day (found by binary search). This problem can be formulated recursively using DP with memoization (or solved iteratively) where dp(i, rem) gives the maximum value we can obtain starting from event index i with rem events left to attend. The final answer is dp(0, k).

Key data structures and methods:

  • Sorted list of events
  • Binary search to jump to the next eligible event (using built-in methods or custom search)
  • 2D DP table (or memoization cache) where the dimensions are the event index and the number of events remaining

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution using recursion and memoization
from bisect import bisect_right
from functools import lru_cache

def maxValue(events, k):
    # Sort events by start day for consistent ordering
    events.sort(key=lambda x: x[0])
    
    # Precompute the start days for binary search
    start_days = [event[0] for event in events]
    n = len(events)
    
    # Define recursive function with memoization
    @lru_cache(maxsize=None)
    def dp(index, remaining):
        # if no events left or reached end, return 0
        if remaining == 0 or index >= n:
            return 0
        
        # Option 1: Skip the current event
        max_val = dp(index + 1, remaining)
        
        # Option 2: Attend the current event
        # Unpack the current event properties
        start, end, value = events[index]
        # Find the next event index using binary search (events with start > end)
        next_index = bisect_right(start_days, end)
        # Adding current event's value and solve subproblem from next eligible event
        max_val = max(max_val, value + dp(next_index, remaining - 1))
        return max_val
    
    return dp(0, k)

# Example usage:
#print(maxValue([[1,2,4],[3,4,3],[2,3,1]], 2))
← Back to All Questions