157. Minimum CPUs Needed for Earliest Tasks Completion

Asked in

Minimum CPUs Needed for Earliest Tasks Completion
You are given a list of task start times and an integer taskLength.

Each task has the same length taskLength.

A task may start at its given start time or at any later time.

A CPU can run at most one task at a time.

Once a task starts on a CPU, it runs continuously for exactly taskLength time units.

Find the minimum number of CPUs needed so that all tasks finish as early as possible.

Return this minimum number of CPUs.

This is not the same as the meeting rooms problem, because tasks are allowed to start later than their given start time.

Method Signature

int minCpusNeeded(List<Integer> startTimes, int taskLength)

Parameters

  • startTimes: a list where startTimes.get(i) is the earliest time at which the ith task may start.
  • taskLength: the length of every task.

Return Value

Return the minimum number of CPUs needed to achieve the earliest possible completion time of the final task.

Task Scheduling Rules

  • Each task may start at or after its given start time.
  • Each task takes exactly taskLength time units.
  • Each CPU can process only one task at a time.
  • Tasks may be assigned to any CPU.
  • The goal is first to minimize the end time of the final task.
  • Among schedules that minimize the final end time, return the minimum number of CPUs required.

Constraints

  • 1 ≤ startTimes.size() ≤ 100,000
  • 0 ≤ startTimes.get(i) ≤ 100,000,000
  • 1 ≤ taskLength ≤ 100,000,000
  • startTimes may contain duplicate values.
  • startTimes is not guaranteed to be sorted.

Examples

Example 1

minCpusNeeded(startTimes = List.of(0, 0, 0, 10000), taskLength = 5)
returns 1

Explanation:
With one CPU, the first three tasks can run from 0 to 5, 5 to 10, and 10 to 15. The final task can still start at 10000 and finish at 10005. Using more CPUs does not improve the final completion time.

Example 2

minCpusNeeded(startTimes = List.of(0, 0, 0), taskLength = 5)
returns 3

Explanation:
The earliest possible final completion time is 5. To finish all three tasks by time 5, all three tasks must run at the same time, so three CPUs are needed.

Example 3

minCpusNeeded(startTimes = List.of(0, 5, 10), taskLength = 5)
returns 1

Explanation:
One CPU can run the tasks from 0 to 5, 5 to 10, and 10 to 15.

Example 4

minCpusNeeded(startTimes = List.of(0, 1, 2), taskLength = 10)
returns 3

Explanation:
The earliest possible final completion time is 12, because the task with earliest start time 2 cannot finish before 12. To finish all tasks by 12, all three tasks need separate CPUs.




Please use Laptop/Desktop or any other large screen to add/edit code.