2054. Two Best Non Overlapping Events

Problem Statement in English

You’re given a 2D integer array events where $events[i] = [startDay_i, endDay_i, value_i]$.

The $i^{th}$ event starts at $startDay_i$ and ends at $endDay_i$, and if you attend this event, you will receive a value of $value_i$.

You can choose to attend at most two non-overlapping events to maximize the sum of their values.

Two events are considered non-overlapping if they do not share any days.

Approach

Since this problem wants us to find a pair of events, we can get away with a very simplistic approach using a min-heap.

All we really do is track the best event that we’ve seen in the past that doesn’t overlap with the current event.

Then as we iterate through the events, we can keep updating our result with the sum of the current event’s value and the best past event’s value.

This can be done by maintaining a min-heap of events sorted by their end days, as well as sorting the events by their start days, for us to iterate through them in order.

Solution in Python

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        minheap = []
        events.sort(key=lambda x: (x[0], x[1]))

        for start, stop, v in events:
            heappush(minheap, (stop, v))

        heapify(minheap)

        res = 0
        pbest = 0

        for start, stop, v in events:
            while minheap and minheap[0][0] < start:
                pstop, pv = heappop(minheap)
                pbest = max(pbest, pv)
            res = max(res, v + pbest)
        
        return res

Complexity

• Time: $O(n \log n)$
  Since we sort the events and use a heap to manage them.

• Space: $O(n)$
  We use a heap to store the events.

Mistakes I Made

I had to look this one up. I was thinking along the lines of dynamic programming, but this heap-based approach is much cleaner, and very straightforward.

And we are done.