Show problems as
Classic problem #1751HardArrayBinary SearchDynamic ProgrammingSorting

Maximum Number of Events That Can Be Attended II

Real-world version: Taking at Most k Bookings
Tracked in this browser only
Read Maximum Number of Events That Can Be Attended II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A hall has bookings on offer. bookings[i] = [first, last, fee] runs from day first to day last, both days included, and pays fee.

Take at most k of them, and no two taken bookings may share a day.

Return the largest total fee that can be earned.

Examples

Example 1

Input
bookings = [[1, 2, 4], [2, 3, 10]], k = 2
Output
10

The two bookings share day 2, so only one may be taken and the larger fee wins.

Example 2

Input
bookings = [[1, 10, 5], [2, 3, 4], [5, 6, 4]], k = 2
Output
8

The long booking pays 5 on its own, while the two short ones share no day and pay 4 each.

Example 3

Input
bookings = [[1, 2, 1], [3, 4, 1], [5, 6, 1], [7, 8, 1]], k = 2
Output
2

The four bookings share no days at all, but only two of them may be taken.

Constraints

  • 1 <= k <= bookings.length
  • 1 <= k * bookings.length <= 10^6
  • bookings[i].length == 3
  • 1 <= bookings[i][0] <= bookings[i][1] <= 10^9
  • 1 <= bookings[i][2] <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_value(bookings: list[list[int]], k: int) -> int:
Java
public int maxValue(int[][] bookings, int k)

More on the same topics