Show problems as
Classic problem #1235HardArrayBinary SearchDynamic ProgrammingSorting

Maximum Profit in Job Scheduling

Real-world version: Studio Booking Payout
Tracked in this browser only
Read Maximum Profit in Job Scheduling on LeetCode(opens in a new tab)

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

A recording studio has a stack of booking requests to answer. Request i wants the room from hour start[i] until hour finish[i] and pays payout[i] if it is accepted.

The room holds one session at a time, so two accepted requests may not overlap. Requests that merely touch are fine: a request that ends at hour t can be followed by one that begins at hour t, because the engineer resets the room instantly.

Accept any collection of requests you like, subject to that rule, and return the largest total payout obtainable. Accepting nothing is allowed but never necessary, since every payout is positive.

Examples

Example 1

Input
start = [1, 3], finish = [3, 5], payout = [6, 6]
Output
12

The second request begins on the hour the first one ends, so both fit and the studio collects everything.

Example 2

Input
start = [1, 1, 3], finish = [10, 3, 6], payout = [20, 12, 12]
Output
24

Two shorter back-to-back sessions beat the single long one that pays 20 and blocks the whole day.

Example 3

Input
start = [1, 2, 3], finish = [8, 7, 9], payout = [5, 9, 3]
Output
9

Every pair of requests overlaps here, so only the best paying one can be taken.

Constraints

  • 1 <= start.length == finish.length == payout.length <= 5 * 10^4
  • 1 <= start[i] < finish[i] <= 10^9
  • 1 <= payout[i] <= 10^4

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_payout(start: list[int], finish: list[int], payout: list[int]) -> int:
Java
public int maxPayout(int[] start, int[] finish, int[] payout)

More on the same topics