Schedule Tasks on Minimum Machines

We are given an array called tasks. Each entry in this array has a start time and an end time for one task.

We are given an array called tasks. Each entry in this array has a start time and an end time for one task.

Our job is to find the minimum number of machines needed to complete all n tasks. A machine can only work on one task at a time, but once it finishes a task, it can immediately start another one.

Minimum Number of Machines Required

Problem Statement

We are given an array called tasks. Each entry in this array has a start time and an end time for one task.

Our job is to find the minimum number of machines needed to complete all n tasks. A machine can only work on one task at a time, but once it finishes a task, it can immediately start another one.

Constraints

• n == tasks.length
• 1 ≤ tasks.length ≤ 10³
• 0 ≤ tasks[i].start < tasks[i].end ≤ 10⁶

Note: No worked examples were shared for this problem. The code does include one sample input, though — [[2,3],[4,7],[8,18],[18,25],[26,30]] — which returns 1, since each task starts only after the previous one ends. Feel free to share proper examples so they can be added here.

Solution 1: Sorting with a Single Min Heap

The idea:

• We store the end time of each running task in a min heap.
• We sort all the tasks by their start time.
• For each task, we check the smallest end time in the heap:
  • If the new task's start time is greater than or equal to that end time, a machine has become free. We remove that end time from the heap (the machine is now reused).
  • We then add the current task's end time to the heap. This represents either a reused machine or a brand new one.
• At the end, the size of the heap tells us how many machines were needed at once — which is our answer.

Code

class Heap {
  constructor(comparator) {
    this.heap = [];
    this.comparator = comparator;
  }
  size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
  peek() { return this.heap[0]; }
  push(val) {
    this.heap.push(val);
    this._up(this.heap.length - 1);
  }
  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._down(0);
    }
    return top;
  }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.comparator(this.heap[p], this.heap[i]) <= 0) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }
  _down(i) {
    const n = this.heap.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let best = i;
      if (l < n && this.comparator(this.heap[l], this.heap[best]) < 0) best = l;
      if (r < n && this.comparator(this.heap[r], this.heap[best]) < 0) best = r;
      if (best === i) break;
      [this.heap[i], this.heap[best]] = [this.heap[best], this.heap[i]];
      i = best;
    }
  }
}

function MachineRequire(tasks) {
  var sortedTasks = tasks.sort((a, b) => a[0] - b[0]);
  let minHeap = new Heap((a, b) => a - b);

  for (let task of sortedTasks) {
    if (!minHeap.isEmpty() && task[0] >= minHeap.peek()) {
      minHeap.pop();
    }
    minHeap.push(task[1]);
  }

  return minHeap.size();
}

console.log(MachineRequire([[2, 3], [4, 7], [8, 18], [18, 25], [26, 30]]));

Solution 2: Using Two Heaps (No Sorting)

The same problem can also be solved using two heaps instead of sorting the array first.

The idea:

• We put all the tasks themselves into a min heap, ordered by their start time.
• We keep a separate min heap called machinesAvailable. This stores machines that have finished their current task, along with the time they became free.
• For each task, taken in order of start time:
  • We check if any machine in machinesAvailable is free by the time this task starts (its free time is less than or equal to the task's start time).
  • If yes, we reuse that machine for the new task.
  • If no, we create a new machine and increase our machine count.
  • Either way, we update the machine's status with the new task's end time, and put it back into machinesAvailable.
• At the end, optimalMachines holds our answer.

Code

import { MinHeap } from "./min_heap.js";

function tasks(tasksList) {
  let optimalMachines = 0;
  let machinesAvailable = new MinHeap();
  tasksList = new MinHeap(tasksList);
  let machineInUse;

  while (tasksList.size()) {
    let task = tasksList.poll();

    if (
      machinesAvailable.size() &&
      task[0] >= machinesAvailable.peek()[0]
    ) {
      machineInUse = machinesAvailable.poll();
      machineInUse = [task[1], machineInUse[1]];
    } else {
      optimalMachines += 1;
      machineInUse = [task[1], optimalMachines];
    }
    machinesAvailable.offer(machineInUse);
  }

  return optimalMachines;
}

Note: This code depends on a MinHeap class from "./min_heap.js" that is not shown here. It seems to support building a heap directly from an array (new MinHeap(tasksList)), along with poll(), peek(), offer(), and size() methods. You may want to include that file's code with this article.