Finish Ordered CPU Tasks with the Fewest CPUs
Updated
Problem statement
For this exercise, assume all tasks are waiting at time 0 and must start in their listed order. Task i takes durations[i] time units on one CPU. A task runs without interruption, and each CPU runs at most one task at a time.
With maxCpus identical CPUs, start the next waiting task as soon as any CPU becomes free. Let T be the time when all tasks have finished. Then find the smallest positive CPU count that follows the same queue rule and finishes by T.
Return [T, smallestCpuCount]. A CPU that finishes a task at time t may start the next task at that same time. CPUs beyond the number of tasks may remain idle.
Function
minimumTaskResources(durations: int[], maxCpus: int) → long[]Examples
Example 1
durations = [3,2,2]maxCpus = 2return = [4,2]The first two tasks start at 0. The second CPU runs the last task during [2,4), so all tasks finish at 4. One CPU would need 7.
Example 2
durations = [5,1,1]maxCpus = 3return = [5,2]Three CPUs finish at 5. Two CPUs also finish at 5 by running the two short tasks consecutively on the second CPU. One CPU needs 7.
Constraints
- 1 <= durations.length <= 10^5
- 1 <= durations[i] <= 10^9
- 1 <= maxCpus <= 10^5
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Shortest-Job-First Process SchedulingByteDance · PHONE SCREENByteDance interview questions
- Meeting Room SchedulerAmazon · PHONE SCREEN
- Dynamic Batch Completion TimesAmbience Healthcare · PHONE SCREEN
- Sorted Insertion SnapshotsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Automation Pipeline, Part 3: Stage DurationPlaid · PHONE SCREENPlaid interview questions
- Split Tender Part 4 - RefundsStripe · OA · PHONE SCREENStripe interview questions
- Running Medians and PercentilesStackAdapt · PHONE SCREENStackAdapt interview questions
- Meeting Rooms IIIBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Online Meeting Scheduler with Fixed RoomsUber · ONSITE INTERVIEWUber interview questions
- Index of the Maximum After Left RotationsChubb · OAChubb interview questions