Advent of PBT 2021 - Day 24

export type Task = {
  taskId: number;
  estimatedTime: number;
  dependsOnTasks: number[];
};

export type ScheduledTask = {
  taskId: number;
  start: number;
  finish: number;
};

/**
 * Christmas is coming! Santa Claus and his elves have to produce all the presents before the D-day.
 * In order to be as efficient as possible they want to schedule and parallelize as many tasks as possible.
 *
 * So they come up with a precise list of all the tasks including their dependencies and the time they will take.
 * Now we have to suggest the ideal timetable to achieve this goal.
 *
 * @param tasks - Define the tasks to achieve.
 * Tasks should not define circular dependencies, one task cannot be dependant on itself (even indirectly).
 *
 * The following implementation is based on the one suggested at https://algs4.cs.princeton.edu/44sp/CPM.java.html.
 * It solves the "parallel precedence-constrained job scheduling problem".
 */
declare function christmasFactorySchedule(tasks: Task[]): ScheduledTask[];

it("should fully parallelize all the tasks whenever possible", () => {
  // Arrange
  const tasks: Task[] = [
    { taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
    { taskId: 1, estimatedTime: 5, dependsOnTasks: [] },
    { taskId: 2, estimatedTime: 3, dependsOnTasks: [] },
    { taskId: 3, estimatedTime: 12, dependsOnTasks: [] }
  ];

  // Act
  const scheduledTasks = christmasFactorySchedule(tasks);

  // Assert
  expect(scheduledTasks).toEqual([
    { taskId: 0, start: 0, finish: 10 },
    { taskId: 1, start: 0, finish: 5 },
    { taskId: 2, start: 0, finish: 3 },
    { taskId: 3, start: 0, finish: 12 }
  ]);
});

it("should queue all tasks whenever no parallel runs are allowed", () => {
  // Arrange
  const tasks: Task[] = [
    { taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
    { taskId: 1, estimatedTime: 5, dependsOnTasks: [2] },
    { taskId: 2, estimatedTime: 3, dependsOnTasks: [3] },
    { taskId: 3, estimatedTime: 12, dependsOnTasks: [0] }
  ];

  // Act
  const scheduledTasks = christmasFactorySchedule(tasks);

  // Assert
  expect(scheduledTasks).toEqual([
    { taskId: 0, start: 0, finish: 10 },
    { taskId: 1, start: 25, finish: 30 },
    { taskId: 2, start: 22, finish: 25 },
    { taskId: 3, start: 10, finish: 22 }
  ]);
});

it("should be able to handle tasks depending on the completion of many", () => {
  // Arrange
  const tasks: Task[] = [
    { taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
    { taskId: 1, estimatedTime: 5, dependsOnTasks: [2] },
    { taskId: 2, estimatedTime: 3, dependsOnTasks: [0, 3] },
    { taskId: 3, estimatedTime: 12, dependsOnTasks: [] }
  ];

  // Act
  const scheduledTasks = christmasFactorySchedule(tasks);

  // Assert
  expect(scheduledTasks).toEqual([
    { taskId: 0, start: 0, finish: 10 },
    { taskId: 1, start: 15, finish: 20 },
    { taskId: 2, start: 12, finish: 15 },
    { taskId: 3, start: 0, finish: 12 }
  ]);
});

it("should be able to handle complex tasks with many dependencies", () => {
  // Arrange
  const tasks: Task[] = [
    { taskId: 0, estimatedTime: 10, dependsOnTasks: [] },
    { taskId: 1, estimatedTime: 5, dependsOnTasks: [2] },
    { taskId: 2, estimatedTime: 3, dependsOnTasks: [0, 3] },
    { taskId: 3, estimatedTime: 12, dependsOnTasks: [4] },
    { taskId: 4, estimatedTime: 1, dependsOnTasks: [] },
    { taskId: 5, estimatedTime: 6, dependsOnTasks: [0] },
    { taskId: 6, estimatedTime: 8, dependsOnTasks: [2, 5] },
    { taskId: 7, estimatedTime: 9, dependsOnTasks: [1, 6] }
  ];

  // Act
  const scheduledTasks = christmasFactorySchedule(tasks);

  // Assert
  expect(scheduledTasks).toEqual([
    { taskId: 0, start: 0, finish: 10 },
    { taskId: 1, start: 16, finish: 21 },
    { taskId: 2, start: 13, finish: 16 },
    { taskId: 3, start: 1, finish: 13 },
    { taskId: 4, start: 0, finish: 1 },
    { taskId: 5, start: 10, finish: 16 },
    { taskId: 6, start: 16, finish: 24 },
    { taskId: 7, start: 24, finish: 33 }
  ]);
});