Maximum Number of Events That Can Be Attended II

Hard
1091.

Maximum Number of Events That Can Be Attended II

Maximum Number of Events That Can Be Attended II is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} events
 * @param {number} k
 * @return {number}
 */
var maxValue = function(events, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Events That Can Be Attended II — Solution

Maximum Number of Events That Can Be Attended II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Events That Can Be Attended II is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.

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

Hints for Maximum Number of Events That Can Be Attended II

  1. Hint 1

    Sort the events by start day, then the choice at each event is simply take or skip.

  2. Hint 2

    Taking event i jumps to the first event starting after end[i] — a binary search.

  3. Hint 3

    dp[i][j] = the best value from event i onward using at most j attendances.

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

  1. Sort the events by start day.
  2. Binary-search each nextFree[i] over the sorted starts.
  3. Fill dp backwards over i and forwards over j, taking the better of skip and take.
  4. 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]

Java

public static int maxValue(int[][] events, int k) {
    int[][] sorted = events.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    int n = sorted.length;
    int[] nextFree = new int[n];
    for (int i = 0; i < n; i++) {
        int lo = i + 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (sorted[mid][0] > sorted[i][1]) hi = mid;
            else lo = mid + 1;
        }
        nextFree[i] = lo;
    }
    int[][] dp = new int[n + 1][k + 1];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = Math.max(dp[i + 1][j], sorted[i][2] + dp[nextFree[i]][j - 1]);
        }
    }
    return dp[0][k];
}

C++

int maxValue(vector<vector<int>>& events, int k) {
    vector<vector<int>> sorted = events;
    sort(sorted.begin(), sorted.end());
    int n = (int) sorted.size();
    vector<int> nextFree(n, n);
    for (int i = 0; i < n; i++) {
        int lo = i + 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (sorted[mid][0] > sorted[i][1]) hi = mid;
            else lo = mid + 1;
        }
        nextFree[i] = lo;
    }
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = max(dp[i + 1][j], sorted[i][2] + dp[nextFree[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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming