Medium

Two Best Non-Overlapping Events

LAB

Given events [start,end,value], return the maximum value from attending at most two non-overlapping events.

EXAMPLES

Example 1

Input
{
  "events": [
    [
      1,
      3,
      2
    ],
    [
      4,
      5,
      2
    ],
    [
      2,
      4,
      3
    ]
  ]
}

Output
4

FUNCTION SHAPE

events: intMatrix→int

SOLUTION NOTE

Precompute suffix max values. For each event, find best event starting after it ends.

Reveal reference solution +

pythonREFERENCE

def maxTwoEvents(self, events: List[List[int]]) -> int:
    events.sort()
    n = len(events)

    # Suffix max value
    suffix_max = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_max[i] = max(events[i][2], suffix_max[i + 1])

    res = 0
    for i in range(n):
        # Take only this event
        res = max(res, events[i][2])

        # Take this event + best non-overlapping
        end = events[i][1]
        j = bisect_left(events, [end + 1, 0, 0])
        if j < n:
            res = max(res, events[i][2] + suffix_max[j])

    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗