0565MediumArrayBinary SearchDynamic ProgrammingSortingHeap (Priority Queue)

Two Studio Bookings

Tracked in this browser only

Trains the technique from

LeetCode 2054Two Best Non-Overlapping Events

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_two_events(events: list[list[int]]) -> int:

Java

public int maxTwoEvents(int[][] events)

The intended approach

Time O(n log n): one sort plus a binary search per request.Space O(n) for the sorted copy and the suffix maxima.

Sort the requests by opening day and build an array holding, for each position, the largest fee among that position and everything after it. Then take each request in turn as the earlier of the pair: a binary search over the opening days locates the first request that opens after this one closes, and the precomputed array gives the best fee available from there on in one read. The array is padded with a zero at the end, which covers the case where no second request fits and the single fee stands on its own.

Pythonentry point: max_two_events

def max_two_events(events):
    # O(n log n) time, O(n) space: sort by opening day, precompute the best fee
    # available from each suffix, then for every booking jump to the first
    # booking that opens after it closes.
    order = sorted(events, key=lambda e: e[0])
    n = len(order)
    starts = [e[0] for e in order]
    best_from = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        best_from[i] = max(best_from[i + 1], order[i][2])
    answer = 0
    for s, e, v in order:
        lo = 0
        hi = n
        while lo < hi:
            mid = (lo + hi) // 2
            if starts[mid] > e:
                hi = mid
            else:
                lo = mid + 1
        total = v + best_from[lo]
        if total > answer:
            answer = total
    return answer

The obvious version

Try every request on its own and every ordered pair of distinct requests, keeping the best total among those that leave no shared day.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_two_events(events):
    best = 0
    n = len(events)
    for i in range(n):
        if events[i][2] > best:
            best = events[i][2]
        for j in range(n):
            if i == j:
                continue
            if events[i][1] < events[j][0]:
                total = events[i][2] + events[j][2]
                if total > best:
                    best = total
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in