In project management there's a method, called the critical path method, that is used for scheduling activities and for determining which activities' timings are crucial (i.e. critical) and for which activities the schedule offers a timing tolerance.
Your program's task is to order a set of activities chronologically and for each of those activities determine their:
- earliest possible start;
- earliest possible finish;
- latest possible start;
- latest possible finish.
Lastly, your program should mark which subsequent activities make up the longest, uninterrupted path; i.e. the critical path.
The input will be the activities by their name, with their duration (in an unspecified time unit) and with the names of the activities they depend on. For this challenge only so-called finish to start dependencies will be presented as input. In other words: any possibly provided dependencies for a given activity signify that said activity can only start when all the activities, that this activity depends on, have finished. No other forms of dependencies will be presented.
The expected input is in the form of (possibly multiples of):
Fsignifies the activity's name; an uppercase alphabetic character;
12signifies the duration as a positive integer;
C,Bsignifies the optional dependencies, as a comma-separated list of activity names.
Here's an example input:
name | duration | dependencies ------+----------+-------------- A | 15 | B | 7 | C | 9 | A,B D | 3 | B,C E | 5 | C F | 11 | D G | 4 | D,E,F
Your program's output will be an ASCII table, in the exact following form, but filled with different data, depending on the input of course (here I'm using the example input, from above, as input):
name | estart | efinish | lstart | lfinish | critical ------+--------+---------+--------+---------+---------- A | 0 | 15 | 0 | 15 | Y B | 0 | 7 | 8 | 15 | N C | 15 | 24 | 15 | 24 | Y D | 24 | 27 | 24 | 27 | Y E | 24 | 29 | 33 | 38 | N F | 27 | 38 | 27 | 38 | Y G | 38 | 42 | 38 | 42 | Y
- the activities are ordered chronologically ascending by
estart(and then arbitrarily);
estartis earliest start;
efinishis earliest finish;
lstartis latest start;
lfinishis latest finish;
Y/Nvalue, signifying whether this activity belongs to the critical path (i.e.
lstart - estart = 0and
lfinish - efinish = 0).
The expected constraints for the input will be:
- The activity names will never exceed
Z; i.e. the total amount of activities will never exceed 26;
- The total duration (i.e. the latest finish of the last activity) will never exceed
9999999(the width of the
lfinishcolumn, with padding);
- The number of dependencies, for any given activity, will never exceed 6;
- The input will never be inconsistent (e.g. no non-existent dependencies, etc.).
The constraints for your program are:
- No use of existing PM/CPM APIs1; you must create the algorithm from scratch.
This is a popularity-contest2; the most elegant solution (or at least, I hope that's what voters will vote for), by popular vote, wins. The winner will be determined 4 days after the submission time of this challenge.
1. If any such API even exists.
2. I want to give the more verbose languages a fair shot at this as well.