2054. Two Best Non-Overlapping Events

[mah-shamim]

Topics: Array, Binary Search, Dynamic Programming, Sorting, Heap (Priority Queue)

You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. 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 <= 105
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 109
• 1 <= valuei <= 106

Hint:

1. How can sorting the events on the basis of their start times help? How about end times?
2. How can we quickly get the maximum score of an interval not intersecting with the interval we chose?

[mah-shamim]

We can use the following approach:

Approach

1. Sort Events by End Time:

   • Sorting helps us efficiently find non-overlapping events using binary search.

2. Binary Search for Non-Overlapping Events:

   • Use binary search to find the latest event that ends before the current event's start time. This ensures non-overlapping.

3. Dynamic Programming with Max Tracking:

   • While iterating through the sorted events, maintain the maximum value of events up to the current one. This allows us to quickly compute the maximum sum of two events.

4. Iterate and Calculate the Maximum Sum:

   • For each event, calculate the possible sum using:
     • Only the current event.
     • The current event combined with the best non-overlapping event found using binary search.

Let's implement this solution in PHP: 2054. Two Best Non-Overlapping Events

<?php
/**
 * @param Integer[][] $events
 * @return Integer
 */
function maxTwoEvents($events) {
    // Step 1: Sort events by end time
    usort($events, function ($a, $b) {
        return $a[1] - $b[1]; // Sort by endTime
    });

    $n = count($events);
    $maxSum = 0;
    $maxUpTo = []; // Maximum value up to index i
    $maxValueSoFar = 0;

    // Step 2: Prepare a list of end times for binary search
    $endTimes = array_column($events, 1);

    // Step 3: Iterate through events
    foreach ($events as $i => $event) {
        $startTime = $event[0];
        $endTime = $event[1];
        $value = $event[2];

        // Use binary search to find the latest non-overlapping event
        $left = 0;
        $right = $i - 1;
        $bestIndex = -1;

        while ($left <= $right) {
            $mid = intval(($left + $right) / 2);
            if ($endTimes[$mid] < $startTime) {
                $bestIndex = $mid; // Potential candidate
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        // If a non-overlapping event is found, use its maximum value
        $currentSum = $value;
        if ($bestIndex != -1) {
            $currentSum += $maxUpTo[$bestIndex];
        }

        // Update the maximum sum found so far
        $maxSum = max($maxSum, $currentSum);

        // Update the max value up to the current index
        $maxValueSoFar = max($maxValueSoFar, $value);
        $maxUpTo[$i] = $maxValueSoFar;
    }

    return $maxSum;
}

// Example Usage:
$events1 = [[1, 3, 2], [4, 5, 2], [2, 4, 3]];
$events2 = [[1, 3, 2], [4, 5, 2], [1, 5, 5]];
$events3 = [[1, 5, 3], [1, 5, 1], [6, 6, 5]];

echo maxTwoEvents($events1) . "\n"; // Output: 4
echo maxTwoEvents($events2) . "\n"; // Output: 5
echo maxTwoEvents($events3) . "\n"; // Output: 8
?>

Explanation:

1. Sorting:

   • The events are sorted by their end time, which allows for efficient searching of the last non-overlapping event.

2. Binary Search:

   • For each event, binary search determines the latest event that ends before the current event starts.

3. Max Tracking:

   • We maintain an array maxUpTo, which stores the maximum value of events up to the current index. This avoids recalculating the maximum for earlier indices.

4. Max Sum Calculation:

   • For each event, calculate the sum of its value and the best non-overlapping event's value. Update the global maximum sum accordingly.

Complexity Analysis

• Sorting: O(n log n)
• Binary Search for Each Event: O(log n), repeated n times → O(n log n)
• Overall: O(n log n)

This solution is efficient and works well within the constraints.

[basharul-siddike]

Thanks to solve the Two Best Non-Overlapping Events problem efficiently

[mah-shamim]

Thanks