Maximum Number of Events That Can Be Attended II

Hard Dynamic Programming 2D DP Original on LeetCode

Reported atSnowflakeGroww

Maximum Number of Events That Can Be Attended II is a hard dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (bottom-up dp + binary search), runs in O(n log n + n · k) time and O(n · k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (pick or skip every event) up.

Problem

You are given an array events where events[i] = [startDay, endDay, value]: the i-th event runs from startDay to endDay, both days included, and attending it earns value. You may attend at most k events.

You can only be at one event at a time, and you must attend an event for its whole duration. That means two chosen events may not share any day: if one ends on day d, the next one must start on day d + 1 or later.

Return the maximum total value you can earn.

Examples

Example 1

Input
events = [[1,3,5],[2,5,9],[4,6,4],[7,8,3]], k = 2
Output
12
Why
Attend [2,5,9] and [7,8,3] for 9 + 3 = 12. Taking [1,3,5] and [4,6,4] gives only 9.

Example 2

Input
events = [[1,4,6],[4,5,8],[6,9,2]], k = 3
Output
10
Why
[1,4] and [4,5] share day 4, so they cannot both be attended. The best is [4,5,8] + [6,9,2] = 10.

Example 3

Input
events = [[1,1,3],[2,2,1],[3,3,7],[1,3,10]], k = 1
Output
10
Why
With only one event allowed, pick the single most valuable one.

Constraints

  • 1 <= k <= events.length
  • 1 <= k · events.length <= 10^6
  • 1 <= startDay <= endDay <= 10^9
  • 1 <= value <= 10^6

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (pick or skip every event)O(2^n · n)O(n)
Optimal (bottom-up DP + binary search)O(n log n + n · k)O(n · k)

1Brute force (pick or skip every event)

TimeO(2^n · n)Each event can be taken or skipped, and every take does a linear scan.
SpaceO(n)Recursion depth is at most n.

Sort events by start day and recursively decide for each event whether to skip it or attend it. Attending one jumps to the first later event that starts after it ends and uses up one of the k slots. The recursion tries every valid selection, so it is exponential.

  1. Sort events by start day.
  2. solve(i, left): if i == n or left == 0 return 0.
  3. skip = solve(i + 1, left).
  4. Scan forward from i + 1 to the first event whose start > events[i].end, call it nx; take = value + solve(nx, left - 1).
  5. Return max(skip, take).
class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (x, y) -> Integer.compare(x[0], y[0]));
        return solve(events, 0, k);
    }

    private int solve(int[][] ev, int i, int left) {
        if (i == ev.length || left == 0) return 0;
        int skip = solve(ev, i + 1, left);
        int nx = i + 1;
        while (nx < ev.length && ev[nx][0] <= ev[i][1]) nx++;
        int take = ev[i][2] + solve(ev, nx, left - 1);
        return Math.max(skip, take);
    }
}

Edge cases to test

  • One event ending on the same day another starts (they overlap)
  • k larger than the number of events that can fit together
  • k = 1, where the answer is just the largest value
  • A long, valuable event competing with several short ones

Hints

Hint 1

Sort the events by start day. For each event you either skip it or attend it; if you attend it, the next event you may consider is the first one starting after it ends.

Hint 2

The state is (index of the next event to consider, how many events you may still attend). That is at most n · k states.

Hint 3

Binary search on the sorted start days finds the next compatible event in O(log n).

FAQ

What is the best time complexity for Maximum Number of Events That Can Be Attended II?

Optimal (bottom-up DP + binary search) runs in O(n log n + n · k) time and O(n · k) extra space. Sorting and n binary searches cost O(n log n); the table has (n + 1)(k + 1) cells, each filled in O(1).

Which pattern does Maximum Number of Events That Can Be Attended II use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Maximum Number of Events That Can Be Attended II?

Yes. Brute force (pick or skip every event) takes O(2^n · n) time and O(n) space. Sort events by start day and recursively decide for each event whether to skip it or attend it.

Which edge cases should I test for Maximum Number of Events That Can Be Attended II?

One event ending on the same day another starts (they overlap); k larger than the number of events that can fit together; k = 1, where the answer is just the largest value; A long, valuable event competing with several short ones.