Two Best Non-Overlapping Events

Medium

Asked by:

25 views

Topics:

ArraysBinary SearchDynamic Programming

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_iand 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 is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

Example 1:

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

Example 2:

Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

Example 3:

Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

Constraints:

2 <= events.length <= 10⁵
events[i].length == 3
1 <= startTime_i <= endTime_i <= 10⁹
1 <= value_i <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of events in the input array, and what is the range of values for the start, end, and value of each event?
Could the events array be empty, or could any of the inner arrays representing events be empty? What should I return in such cases?
If multiple pairs of non-overlapping events yield the same maximum total value, is any one of them acceptable as a valid output?
Are the events sorted by their start times, or do I need to consider unsorted events?
Can events have the same start time and/or end time, and if so, how should that be handled when determining overlap?

Brute Force Solution

Approach

We're trying to find the two best events that don't happen at the same time. The brute force approach involves checking every possible pair of events to see if they overlap, and if they don't, adding up their values to see which pair gives us the highest combined value.

Here's how the algorithm would work step-by-step:

Look at the very first event in the list.
Pair it up with every other event in the list, one at a time.
For each pair, check if the events overlap in time. If they do, ignore that pair.
If the two events don't overlap, add their values together.
Remember the highest total value you've found so far from non-overlapping events.
Now, move to the second event in the list and repeat the process, pairing it with every other event (including events you already checked with the first event).
Continue this process, going through each event in the list and pairing it with all the other events.
After checking every possible pair, the highest total value you remembered is the answer.

Code Implementation

def max_two_non_overlapping_events_brute_force(events):
    max_combined_value = 0

    for first_event_index in range(len(events)):
        for second_event_index in range(len(events)):
            # Avoid comparing the same event with itself
            if first_event_index == second_event_index:
                continue

            first_event_start_time = events[first_event_index][0]
            first_event_end_time = events[first_event_index][1]
            first_event_value = events[first_event_index][2]

            second_event_start_time = events[second_event_index][0]
            second_event_end_time = events[second_event_index][1]
            second_event_value = events[second_event_index][2]

            # Check if the events overlap
            if not (first_event_end_time <= second_event_start_time or \
                    second_event_end_time <= first_event_start_time):
                continue

            # Found two non-overlapping events
            combined_value = first_event_value + second_event_value

            # Update the maximum value
            max_combined_value = max(max_combined_value, combined_value)

    return max_combined_value

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n events in the list. For each event, it then compares it with every other event in the list to check for overlaps. This comparison results in a nested loop structure. Consequently, the time complexity involves comparing each event with roughly n other events, leading to approximately n * n/2 operations. Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The described brute force algorithm only uses a few variables: loop counters for iterating through events, a variable to store the current pair's combined value, and a variable to store the highest combined value seen so far. The number of these variables is constant and does not depend on the number of events, N. Therefore, the auxiliary space used by this algorithm is constant, resulting in O(1) space complexity.

Optimal Solution

Approach

To find the two best non-overlapping events, we want to avoid checking every single pair. The efficient strategy involves pre-calculating the best possible event score up to any given point and then using this information to quickly find the best non-overlapping pair.

Here's how the algorithm would work step-by-step:

First, we'll sort the events based on their ending times. This helps us find events that can potentially come before others without overlapping.
Then, we'll go through the sorted events and keep track of the best event we've seen so far for each ending time. This means, for any point in time, we know the highest score achievable up to that moment.
Next, we'll go through the events again. For each event, we'll look for the best event that ends before it starts (using the info from the previous step). This gives us the best non-overlapping event that could come before our current event.
Now, for each event, calculate the total score by adding its score to the score of the best non-overlapping event that comes before it (if any).
Finally, we find the maximum of these total scores. This maximum score represents the best possible combination of two non-overlapping events.

Code Implementation

def two_best_non_overlapping_events(events):
    # Sort events based on end times.
    events.sort(key=lambda event: event[1])

    max_value_at_time = {}
    best_value_so_far = 0

    # Precompute the maximum event value up to each end time.
    for start_time, end_time, event_value in events:
        best_value_so_far = max(best_value_so_far, event_value)
        max_value_at_time[end_time] = best_value_so_far

    max_two_events_value = 0

    for start_time, end_time, event_value in events:
        # Find the best non-overlapping event before the current event.
        best_previous_event_value = 0
        for previous_end_time in max_value_at_time:
            if previous_end_time <= start_time:
                best_previous_event_value = max(best_previous_event_value, max_value_at_time[previous_end_time])

        # Update the maximum value of two non-overlapping events.
        current_two_events_value = event_value + best_previous_event_value
        max_two_events_value = max(max_two_events_value, current_two_events_value)

    # Return the maximum value of two non-overlapping events.
    return max_two_events_value

Big(O) Analysis

Time Complexity

O(n log n) – The solution begins by sorting the events based on their ending times, which takes O(n log n) time. Then, it iterates through the sorted events twice. The first iteration computes the maximum event score up to each ending time in O(n) time. The second iteration, for each event, finds the best non-overlapping event that ends before it. This step can be done in O(n) time by iterating through the best ending scores we already computed. Consequently, the dominant operation is the initial sorting step, resulting in an overall time complexity of O(n log n).

Space Complexity

O(N) – The algorithm sorts the input array of events, which may take O(N) auxiliary space depending on the sorting algorithm used (e.g., merge sort). Additionally, it maintains an array to store the best event score up to each ending time, requiring O(N) space where N is the number of events. Therefore, the dominant space complexity comes from these auxiliary data structures, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty events array	Return 0 or an appropriate default value, indicating no events can be selected.
Events array with only one event	Return the value of the single event since there is nothing to compare it to for overlaps.
All events overlap with each other	Return the maximum value of a single event since no two non-overlapping events exist.
Very large event values leading to potential integer overflow	Use a data type with sufficient range (e.g., long) to store intermediate sums.
Events sorted in reverse order of start time	The algorithm should correctly handle reverse-sorted input without relying on any pre-sorted assumptions.
Maximum size array	Ensure algorithm scales to handle max input size by using efficient algorithms like dynamic programming or binary search where needed to avoid excessive computation.
Events with identical start and end times but different values	The algorithm needs to correctly iterate and consider all possible event values for optimal selection despite the duplicated start/end times.
Events with very close start and end times causing floating point precision issues if used	The algorithm should rely on integers and discrete comparison for event times, avoiding floating point math for these properties entirely.

Empty events array

How to Handle:

Return 0 or an appropriate default value, indicating no events can be selected.

Events array with only one event

How to Handle:

Return the value of the single event since there is nothing to compare it to for overlaps.

All events overlap with each other

How to Handle:

Return the maximum value of a single event since no two non-overlapping events exist.

Very large event values leading to potential integer overflow

How to Handle:

Use a data type with sufficient range (e.g., long) to store intermediate sums.

Events sorted in reverse order of start time

How to Handle:

The algorithm should correctly handle reverse-sorted input without relying on any pre-sorted assumptions.

Maximum size array

How to Handle:

Ensure algorithm scales to handle max input size by using efficient algorithms like dynamic programming or binary search where needed to avoid excessive computation.

Events with identical start and end times but different values

How to Handle:

The algorithm needs to correctly iterate and consider all possible event values for optimal selection despite the duplicated start/end times.

Events with very close start and end times causing floating point precision issues if used

How to Handle:

The algorithm should rely on integers and discrete comparison for event times, avoiding floating point math for these properties entirely.