Topological Sort - Task Scheduling 2 - Wrong Expected Output for Test Case #3

[ChrisBenka]

Input: abbreviate bricks cardinals dextrous fibre green height 1 1 1 1 1 100 1 5 abbreviate bricks cardinals bricks dextrous bricks bricks fibre green fibre

Expected output should be 102 not 101.

our graph levels looks like: Level 1 = {abbreviation, cardinals, dexterous,green} Level 2 = {bricks} Level 3 = {fibre}

Here {abbreviation, cardinals, and dextrous} are the child of bricks {green} is the child of {fibre} {bricks} is the child of {fibre}

Our levels to the topological sort are: min level 1 = 1 min level 2 = 100 min level 3 = 1

summing together = 102

[luyohuii]

101 is indeed the correct answer, only the finish time matters and not the start time

[t-payne]

I initially was confused about this as well and wanted to offer another explanation in case anyone else comes here with a similar question.

We are able to start the abbreviation, cardinals, dexterous, and green tasks at t=0. The abbreviation, cardinals, and dexterous tasks are all finished at t=1. After these are completed, bricks can be started (while green is still being worked on). bricks finishes at t=2, and then we have to wait 98 more units of time until green finishes before starting fibre. Once green finishes at t=100, fibre takes 1 unit of time to complete at t=101. So, the minimum units of time that pass from start to finish is 101.