Given a set of n number of tasks, implement a task scheduler method, to run in O(n log n) time that finds the minimum number of machines required to complete these n tasks.

1-schedule-tasks.js

// tasksList is an array of tuples [startTime, endTime]
export function tasks(tasksList) {
  // keep our tasks in min-heap, with task with earliest start time on top
  const tasksHeap = new TupleHeap();
  // keep our machines in min heap, with machine whose task finishes earliest on top
  const machinesHeap = new Heap();

  // push all our tasks into min heap
  for (let i = 0; i < tasksList.length; ++i) {
    tasksHeap.push(tasksList[i]);
  }

  while (tasksHeap.length() > 0) {
    // pop the earliest starting task
    const [startTime, endTime] = tasksHeap.deleteTop();
    // if there are no machines, or,
    // if machine whose task ends the earliest still ends after our current task start,
    // allocate a new machine
    if (machinesHeap.length() === 0 || machinesHeap.peekTop() > startTime) {
      machinesHeap.push(endTime);
    } else if (startTime >= machinesHeap.peekTop()) {
      // this task can be processed in the top machine, so we update it's end time
      machinesHeap.deleteTop();
      machinesHeap.push(endTime);
    }
  }

  return machinesHeap.length();
}

2-README.md