2054.two-best-non-overlapping-events.md

2054. Two Best Non-Overlapping Events

TODO: Check the "Solution" section on LeetCode.

Greedy + Enumeration

We sort the events by end time, so that for any given event, we can efficiently find a previous non-overlapping event to pair with.

Then iterate each event, and try to pair it with the previous non-overlapping event. To efficiently find the previous non-overlapping event, we can use binary search to find the last event that ends before the current event starts.

Let's run through the example:

// Sorted by `end` time
   1, 2, 3, 4, 5   value
A: |-----|         2
B:    |-----|      3
C:          |--|   2

Then iterate events:

• Maintain prefix max seen so far: prefixMax[end] indicates the max value seen so far at end time. It is used to find the previous non-overlapping event with the maximum value. For example, prefixMax[4] = 3 means that all intervals before 4 ends have a max value of 3.

// Sorted by `end` time
   1, 2, 3, 4, 5   value, max
A: |-----|         2      2 // prefixMax[3] = 2
B:    |-----|      3      3 // prefixMax[4] = 3
C:          |--|   2      3 // prefixMax[5] = 3

• Find the previous non-overlapping event using binary search by searching for the prefix max of start - 1. Consider pairing the current event with the previous non-overlapping event, or not pairing it at all (if no previous non-overlapping event is found).

For example, for event C [4, 5], value = 2, we search for the prefix max of 4 - 1 = 3, and find that prefixMax[3] = 2, we can pair (2 + 2 = 4) with C or just take C's value 2.

// Sorted by `end` time
   1, 2, 3, 4, 5   value, max
A: |-----|         2      2 // prefixMax[3] = 2
B:    |-----|      3      3 
   <-----* // search for 4 - 1 = 3, prefixMax[3] = 2
C:          |--|   2      3  [i]

fun maxTwoEvents(events: Array<IntArray>): Int {
    // Sort events by end time
    events.sortBy { it[1] }
    
    // Create arrays to store end times and maximum values
    val n = events.size
    val endTimes = IntArray(n)
    val maxValues = IntArray(n)
    
    // Current max value seen so far
    var max = 0
    // The answer
    var maxSum = 0
    
    // Process events and build the arrays
    for (i in 0 until n) {
        val (start, end, value) = events[i]
        
        // Find the previous non-overlapping event using binary search
        val prevIndex = findLastNonOverlapping(endTimes, i, start - 1)
        
        if (prevIndex != -1) {
            // If found a valid previous event, consider pairing
            maxSum = maxOf(maxSum, maxValues[prevIndex] + value)
        } else {
            // No valid previous event, just consider this event alone
            maxSum = maxOf(maxSum, value)
        }
        
        // Update the maximum value seen so far
        max = maxOf(max, value)
        
        // Store the end time and maximum value for this position
        endTimes[i] = end
        maxValues[i] = max
    }
    
    return maxSum
}

// Binary search to find the last event that <= target (lower bound)
private fun findLastNonOverlapping(nums: IntArray, currentIndex: Int, target: Int): Int {
    var left = 0
    var right = currentIndex - 1
    
    while (left <= right) {
        val mid = left + (right - left) / 2
        if (nums[mid] <= target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

// Or equivalently, we can use `TreeMap` to store prefix max values, and use `floorKey` to find the previous non-overlapping event.
fun maxTwoEvents(events: Array<IntArray>): Int {
    events.sortBy { it[1] }
    val prefixMax = TreeMap<Int, Int>()
    var max = 0
    var maxSum = 0
    for ((start, end, value) in events) {
        val previousKey = prefixMax.floorKey(start - 1)
        if (previousKey != null) {
            val previousMax = prefixMax[previousKey]!!
            maxSum = maxOf(previousMax + value, maxSum)
        } else {
            maxSum = maxOf(maxSum, value)
        }
        max = maxOf(max, value)
        prefixMax[end] = max
    }
    return maxSum
}