Solution: Schedule Tasks on Minimum Machines

Let’s solve the Schedule Tasks on Minimum Machines problem using the Heaps pattern.

We'll cover the following

Statement

We are given an input array, tasks, where tasks[i] =[starti,endi]= [start_i, end_i] represents the start and end times of nn tasks. Our goal is to schedule these tasks on machines given the following criteria:

  1. A machine can execute only one task at a time.

  2. A machine can begin executing a new task immediately after completing the previous one.

  3. An unlimited number of machines are available.

Find the minimum number of machines required to complete these nn tasks.

Constraints:

  • n==n == tasks.length

  • 1≤1 \leq tasks.length ≤103\leq 10^3

  • 0≤0 \leq tasksi.start << tasksi.end ≤104\leq 10^4

Solution

The core intuition for solving this problem is to allocate tasks to the minimum number of machines by reusing machines whenever possible. The algorithm efficiently manages machine availability by sorting tasks by their start times and using a min heap to track end times. If the earliest available machine (top of the heap) finishes before or as a task starts, it is reused and removed from the heap. Otherwise, a new machine is allocated, and the current task’s end time is pushed into the heap. The heap size at the end represents the minimum number of machines required.

Using the intuition above, we implement the algorithm as follows:

  1. Sort the tasks array by the start time of each task to process them in chronological order.

  2. Initialize a min heap (machines) to keep track of the end times of tasks currently using machines.

  3. Iterate over each task in the sorted tasks array.

    1. Extract the start and end times of the current task.

    2. Check if the machine with the earliest finish time is free, i.e., top of machines is less than or equal to the current task’s start time. If it is, remove it from the heap, as the machine can be reused.

    3. Push the end time of the current task into the heap, indicating that a machine is now in use until that time.

  4. After processing all tasks, return the size of the heap, which represents the minimum number of machines required.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.