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

Two Best Non-Overlapping Events

Number: 2164

Difficulty: Medium

Paid? No

Companies: Google, Amazon, razorpay

Problem Description

Given an array of events where each event is represented as [startTime, endTime, value], choose at most two non-overlapping events (i.e. the second event must start strictly after the first event ends) so that the sum of their values is maximized. Return the maximum possible sum.

Key Insights

  • Sort events by start time. This allows for binary search to quickly find the next non-overlapping event.
  • Precompute a suffix maximum array where each position stores the maximum event value among all events starting from that index.
  • For each event, via binary search, determine the earliest event that can be attended after the current one, and combine the current event’s value with the best value from the remainder of the list.
  • Consider the case where taking a single event is optimal.

Space and Time Complexity

Time Complexity: O(n log n) – O(n log n) for sorting and binary search over each event. Space Complexity: O(n) – for the auxiliary arrays used (start times and suffix maximum values).

Solution

The algorithm sorts the events by their start time. Then, it builds an array that holds the maximum event value from any index to the end (suffix max). For each event, a binary search is used on the sorted start times to find the next event that can be attended (i.e., the event whose start time is at least the current event's end time plus one). The value of the current event is added to the precomputed best value from that next event, and the maximum sum is updated accordingly. This approach ensures that the best combination of two non-overlapping events is found while keeping complexity under control.

Code Solutions

import bisect
from typing import List

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        # Sort events by their start time
        events.sort(key=lambda x: x[0])
        n = len(events)
        # Extract start times to use for binary search later
        start_times = [event[0] for event in events]
        # Build a suffix max array: suffix_max[i] holds the max event value from events[i] to end
        suffix_max = [0] * n
        suffix_max[-1] = events[-1][2]
        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(events[i][2], suffix_max[i + 1])
        max_value = 0
        # Iterate over each event and use binary search to find the next non-overlapping event
        for i in range(n):
            current_value = events[i][2]
            # Find the first event starting at or after events[i][1] + 1
            next_index = bisect.bisect_left(start_times, events[i][1] + 1)
            if next_index < n:
                current_value += suffix_max[next_index]
            max_value = max(max_value, current_value)
        return max_value
← Back to All Questions