Maximum Number of Events That Can Be Attended II — Hard Problem & Solution

events[i] = [start, end, value] describes an event running from day start to day end inclusive, worth value.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Sorting, Binary Search
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

events[i] = [start, end, value] describes an event running from day start to day end inclusive, worth value. Attending an event means attending it in full, and you cannot attend two events that share any day — the next event must start strictly after the previous one ends.

Attend at most k events and return the maximum total value.

Example 1

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Attend `[1,2,4]` and `[3,4,3]`.

Example 2

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: The single event worth 10 beats any pair.

Example 3

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Take the three most valuable.

Constraints

1 <= k <= events.length <= 10^6
1 <= k * events.length <= 10^6
1 <= starti <= endi <= 10^9
1 <= valuei <= 10^6

How to solve Maximum Number of Events That Can Be Attended II

Sort by start day. For each event precompute nextFree[i], the index of the first event starting strictly after event i ends. Then dp[i][j] = max(dp[i+1][j], value[i] + dp[nextFree[i]][j-1]) — skip or take.

Approach

Sort the events by start day.
Binary-search each nextFree[i] over the sorted starts.
Fill dp backwards over i and forwards over j, taking the better of skip and take.
Return dp[0][k].

Why it works

Sorting by start is what makes nextFree a forward jump rather than a search over the whole set — every compatible successor lies in a contiguous suffix, so one binary search names the whole set of them. The j - 1 on the take branch is the attendance budget, which is why the DP needs two dimensions rather than the single one a plain weighted-interval-scheduling problem would use.

Complexity

Time — O(n log n + n · k)
Space — O(n · k)

Pitfalls

The events are inclusive at both ends, so the successor must start strictly after the end day.
Sorting by end day instead makes the jump index wrong.
At most k — fewer is allowed, which the skip branch already covers.

Reference solution

Python

from bisect import bisect_right
from typing import List

def maxValue(events: List[List[int]], k: int) -> int:
    events = sorted(events)
    n = len(events)
    starts = [e[0] for e in events]
    next_free = [bisect_right(starts, e[1]) for e in events]
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(1, k + 1):
            dp[i][j] = max(dp[i + 1][j], events[i][2] + dp[next_free[i]][j - 1])
    return dp[0][k]

JavaScript

var maxValue = function(events, k) {
    var sorted = events.slice();
    sorted.sort(function(a, b) { return a[0] - b[0]; });
    var n = sorted.length, i, j;
    var nextFree = [];
    for (i = 0; i < n; i++) {
        var lo = i + 1, hi = n;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (sorted[mid][0] > sorted[i][1]) hi = mid; else lo = mid + 1;
        }
        nextFree.push(lo);
    }
    var dp = [];
    for (i = 0; i <= n; i++) {
        var row = [];
        for (j = 0; j <= k; j++) row.push(0);
        dp.push(row);
    }
    for (i = n - 1; i >= 0; i--) {
        for (j = 1; j <= k; j++) {
            var skip = dp[i + 1][j];
            var take = sorted[i][2] + dp[nextFree[i]][j - 1];
            dp[i][j] = skip > take ? skip : take;
        }
    }
    return dp[0][k];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue