Show problems as
Classic problem #2054MediumArrayBinary SearchDynamic ProgrammingSortingHeap (Priority Queue)

Two Best Non-Overlapping Events

Real-world version: Two Studio Bookings
Tracked in this browser only
Read Two Best Non-Overlapping Events on LeetCode(opens in a new tab)

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

A recording studio has a list of booking requests. Request i is given as events[i] = [startDay_i, endDay_i, fee_i]: it occupies the studio from startDay_i to endDay_i inclusive and pays fee_i.

The studio will accept at most two requests. Two accepted requests may not share a day, so one of them has to close strictly before the other opens: if a request closes on day d, the other one may open on day d + 1 at the earliest. Accepting a single request is allowed, and so is accepting none.

Return the largest total fee the studio can collect.

Examples

Example 1

Input
events = [[6, 9, 40], [1, 4, 30], [3, 8, 90]]
Output
90

The request paying 90 runs from day 3 to day 8, which shares days with both of the others, so it is accepted on its own and the studio collects 90.

Example 2

Input
events = [[1, 3, 10], [3, 5, 20]]
Output
20

Both requests want day 3, so only one can be accepted, and the better fee is 20.

Example 3

Input
events = [[1, 3, 10], [4, 5, 20]]
Output
30

The first closes on day 3 and the second opens on day 4, so both fit and the studio collects 30.

Constraints

  • 2 <= events.length <= 10^5
  • events[i].length == 3
  • 1 <= startDay_i <= endDay_i <= 10^9
  • 1 <= fee_i <= 10^6
  • The answer never exceeds 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_two_events(events: list[list[int]]) -> int:
Java
public int maxTwoEvents(int[][] events)

More on the same topics