Schedule Tasks on Minimum Machines

Understand how to schedule multiple tasks on the least number of machines by leveraging heaps to track ongoing tasks. This lesson helps you develop a methodical approach to allocate tasks efficiently, ensuring no overlaps and using unlimited machines selectively to minimize their count.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

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

A machine can execute only one task at a time.
A machine can begin executing a new task immediately after completing the previous one.
An unlimited number of machines are available.

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

Constraints:

$n ==$ tasks.length
$1 \leq$ tasks.length $\leq 10^3$
$0 \leq$ tasks_i.start $<$ tasks_i.end $\leq 10^4$

Examples

JavaScript

usercode > main.js

import { MinHeap, MaxHeap } from './Heap.js'

/* The following definition is for MinHeap.

  You can use the same methods for MaxHeap.
  class MinHeap {

    size();          // return number of elements
    peek();          // return top element without removing
    push(val);       // insert element
    pop();           // remove and return top element
  }
*/

function minimumMachines(tasks){
  
    // Replace this placeholder return statement with your code
    return -1
}

export { 
    minimumMachines
}

Schedule Tasks on Minimum Machines

Schedule Tasks on Minimum Machines

Statement

Examples

Understand the problem

Figure it out!

Try it yourself