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 } ]); });