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

Two Best Non-Overlapping Events

Difficulty: Medium

Problem Description

You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The i-th event starts at startTime_i and ends at endTime_i, and if you attend this event, you will receive a value of value_i. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized. Return this maximum sum. Note that the start time and end time are inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time.

Key Insights

  • Events are represented by their start and end times along with a value.
  • To maximize the sum of values from two non-overlapping events, we need to consider the timing of the events.
  • Sorting the events by their end times allows for efficient comparisons when determining non-overlapping pairs.
  • A binary search approach can quickly find the last non-overlapping event for a given event.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the events and binary searching. Space Complexity: O(n) - for storing sorted events.

Solution

To solve the problem, we will:

  1. Sort the events based on their end times.
  2. Use an array to keep track of the maximum value obtainable up to each event.
  3. For each event, use binary search to find the last event that does not overlap with the current one.
  4. Calculate the potential maximum value by considering the current event and the best non-overlapping event found via binary search.
  5. Return the maximum value obtained from considering all events.

Code Solutions

def maxTwoEvents(events):
    # Sort events by end time
    events.sort(key=lambda x: x[1])
    
    # Array to store the maximum value obtainable up to each event
    max_value_up_to = [0] * len(events)
    for i in range(len(events)):
        max_value_up_to[i] = events[i][2]  # Initial value is the value of the event itself

    # Populate the max_value_up_to array
    for i in range(len(events)):
        for j in range(i):
            if events[j][1] < events[i][0]:  # Non-overlapping condition
                max_value_up_to[i] = max(max_value_up_to[i], max_value_up_to[j] + events[i][2])

    return max(max_value_up_to)
← Back to All Questions