Schedule Tasks on Minimum Machines

Explore how to determine the minimum number of machines required to schedule tasks without overlap by using heaps. This lesson helps you apply heap-based algorithms to optimize task scheduling and manage dynamic intervals effectively.

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