Hard

Maximum Number of Events That Can Be Attended II

LAB

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

EXAMPLES

Example 1

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

Output
7

FUNCTION SHAPE

events: intMatrixk: int→int

SOLUTION NOTE

Sort by start time. For each event, binary search for next non-overlapping event.

Reveal reference solution +

pythonREFERENCE

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

    @cache
    def dp(i, remaining):
        if i == n or remaining == 0:
            return 0

        # Skip this event
        res = dp(i + 1, remaining)

        # Attend this event - find next non-overlapping
        end = events[i][1]
        j = bisect_left(events, [end + 1, 0, 0])
        res = max(res, events[i][2] + dp(j, remaining - 1))

        return res

    return dp(0, k)

TimeO(n × k × log n)

SpaceO(n × k)

Open on LeetCode ↗