Unit Jobs with Deadlines and Profits
Updated
Problem statement
Schedule a subset of jobs on one machine. Each row is [deadline,profit]. Every job takes one time unit, all jobs are available at time zero, and only one job may run in a time slot. Slot 1 finishes at time 1, slot 2 at time 2, and so on.
A job earns its profit only if it finishes at or before its deadline. Choose a feasible subset with the largest total profit. Among schedules with the same maximum profit, choose one completing the largest number of jobs. Return [completedCount,totalProfit]. An empty job list returns [0,0].
This is the classic job-scheduling question in its unit-duration deadline/profit form.
Function
scheduleDeadlineJobs(jobs: int[][]) → int[]Examples
Example 1
jobs = [[2,100],[1,19],[2,27],[1,25],[1,15]]return = [2,127]Schedule the job earning 27 in slot 1 and the job earning 100 in slot 2. At most two jobs can finish by these deadlines, and no other pair earns more than 127.
Example 2
jobs = [[1,0],[2,0],[2,0]]return = [2,0]All schedules earn zero. The tie rule chooses two jobs, filling slots 1 and 2.
Constraints
- For this exercise, assume
0 <= jobs.length <= 1000. - Each row has exactly two integers
[deadline,profit], with1 <= deadline <= 10000and0 <= profit <= 10000. - Each job requires one complete time slot, and a selected job must finish by its deadline.
More JP Morgan Chase Online Assessment questions
- Find Total CostOA · Seen Oct 2026
- Minimum Meeting RoomsOA · Seen Oct 2026
- Count Dropped RequestsOA · Seen Oct 2026
- Maximize Minimum Deployment DifficultyOA · Seen Oct 2026
- Task SchedulingOA · Seen Oct 2026
- Substring RemovalOA · Seen Oct 2026
- Maximum Game Board ScoreOA · Seen Sep 2026
- Minimum Digit Changes Between String HalvesOA · Seen Sep 2026
- Same Substring Within BudgetOA · Seen Sep 2026
- Invert Ad Visibility BitsOA · Seen Aug 2026
Similar questions at other companies
- Find Minimum TimeAlphaSense · OA
- Find Minimum TimeBlackRock · OABlackRock interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Minimum Cost of Every K-Capable Model SetTikTok · OATikTok interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximum Alternating-Index Packet ValueInfosys · OAInfosys interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
Interview reports that mention this question
JP Morgan Chase interview experiences
- JPMorgan Quant Stats Superdays: 3 Experiences (Part 3 of 3)
- JPMorgan Quant Modeling Superdays: 7 Experiences (Part 2 of 3)
- JPMorgan Quant Intern Superday: 19 Experiences (Part 1 of 3)
- JP Morgan Chase Data and AI Intern Superday: 11 Experiences
- JPMorgan Code for Good India 2024: 6 Experiences (Part 5 of 5)