Schedule Unit-Time Jobs for the Most Profit
Updated
Problem statement
You have n jobs. Job i has a deadline deadlines[i] and a profit profits[i].
Time is split into seconds numbered 1, 2, 3, and so on. Every job takes exactly one second, and only one job can run in each second. Job i earns profits[i] if it runs in a second whose number is at most deadlines[i].
Each job runs at most once, and you may skip any job. A skipped job earns nothing. Choose which jobs to run and in which seconds, then return the largest total profit you can earn.
The total can be larger than a 32-bit integer can hold.
Function
maxJobProfit(deadlines: int[], profits: int[]) → longExamples
Example 1
deadlines = [2,1,2,1]profits = [50,10,40,30]return = 90No deadline is later than 2, so at most two jobs can run: one in second 1 and one in second 2. Run the job worth 40 in second 1 and the job worth 50 in second 2. Both finish by their deadline of 2. The total is 40 + 50 = 90. Picking a deadline-1 job instead would mean giving up 40 or 50 for at most 30.
Example 2
deadlines = [1,1,3,3,3]profits = [20,25,5,10,8]return = 43Two jobs have deadline 1, but only one job fits in second 1. Run the one worth 25 there. Seconds 2 and 3 take the two best deadline-3 jobs, worth 10 and 8. The total is 25 + 10 + 8 = 43.
Example 3
deadlines = [1000000000,2]profits = [6,9]return = 15A deadline can be far larger than the number of jobs. Run the job worth 9 in second 1 and the job worth 6 in second 2. Both are on time, so the total is 6 + 9 = 15.
Constraints
1 <= deadlines.length <= 2000profits.length == deadlines.length1 <= deadlines[i] <= 10^91 <= profits[i] <= 10^9
More Scale AI Phone Screen questions
- Four-Player Trick-Taking Card Game SimulationOA · PHONE SCREEN · Seen Aug 2026
- Task Processor: Dependencies and DeadlinesPHONE SCREEN · Seen Aug 2026
- Best Poker Category with a JokerPHONE SCREEN · ONSITE INTERVIEW · Seen Jun 2026
- Free Time for Every Meeting RoomPHONE SCREEN · Seen Apr 2026
- Free Windows Between Busy IntervalsOA · PHONE SCREEN · Seen Apr 2026
- Order Queries by Shortest Processing TimePHONE SCREEN · Seen Apr 2026
- Party Time by Town and Quiet Gaps by CityPHONE SCREEN · Seen Jan 2026
- Party Windows and Dead Zone TimePHONE SCREEN · Seen Oct 2025
- Overlap Duration of Two Time IntervalsPHONE SCREEN · Seen Jun 2025
- Multi-Head Attention BlockPHONE SCREEN · Seen Mar 2025
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Maximum Number of Events That Can Be AttendedSnowflake · PHONE SCREENSnowflake interview questions
- Minimum Meeting RoomsSentry · PHONE SCREENSentry interview questions
- IPOTekion · PHONE SCREENTekion interview questions
- IPOInMobi · PHONE SCREENInMobi interview questions
- Lexicographically Smallest Array with K-Limited Right MovesGoogle · PHONE SCREENGoogle interview questions
- Minimum Refueling StopsBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Select K Paired Indices for Maximum ScoreAmazon · ONSITE INTERVIEW