All problems

Studio Booking Gap

Hard · dynamic programming

A recording studio has one room and a list of booking requests. Each request is [start, end, fee]: the band wants the room from minute start until minute end, and the studio is paid fee if it accepts.

The studio can only host one session at a time, and after every session the room needs gap minutes to be reset. So if one accepted session ends at minute e, the next accepted session must start at minute e + gap or later. With gap = 0 a session may start at the very minute the previous one ends.

Requests are accepted in full or not at all. Return the largest total fee the studio can earn.

Examples

Example 1

Input: bookings = [[1, 3, 5], [2, 5, 6], [4, 6, 5]], gap = 0

Output: 10

Accept the sessions from 1 to 3 and from 4 to 6 for 5 + 5. The middle one pays 6, which is less.

Example 2

Input: bookings = [[1, 3, 5], [2, 5, 6], [4, 6, 5]], gap = 2

Output: 6

After the session ending at 3 the room is free again only from minute 5, so no second session fits there. The best single session pays 6.

Example 3

Input: bookings = [[0, 2, 4], [5, 8, 3], [9, 12, 7]], gap = 3

Output: 11

The first and third sessions fit together because 9 is at least 2 + 3. The second would block the third, since 8 + 3 = 11 is later than 9.

Constraints