Class Name: AlienTakeover
Method Name: takeOverTime
Parameters: String[]
Returns: int
Zorono is the King of an alien tribe planning to take over Earth. Taking over
Earth consists of many tasks, some tasks cannot occur until other tasks are
complete. Each task has a specified duration - the time it takes the task to
complete. Conveniently, Zorono's alien kingdom has infinite labor and
resources, so as many tasks as necessary can be done simultaneously.
Zorono wants a timetable for how long it will take the alien tribe to
completely takeover the Earth and has hired you to write a program to give him
his timetable.
Implement a class AlienTakeover, which contains a method takeOverTime. The
method takes a String[] as a parameter. The String[] contains information on
all the tasks that must be performed, the length of the tasks, and which tasks
must be completed before other tasks. The method returns the minimum length of
time, in hours, the takeover will take (all tasks are completed).
ArrayList elements are of the form:
"TASKNAME LENGTH D1,D2,..."
Where:
*TASKNAME is the name of the task containing between 1 and 20 letters and
*LENGTH is the integer length of time the task takes, in hours between 1 and
100 and
*D1,D2,... is the dependency list - a list of task names seperated by commas
that must be performed before the task can begin. Repeat task names in the same
list should be ignored.
If the task depends on no other tasks, LENGTH is the last item in the String[]
element.
There is exactly 1 space between TASKNAME and LENGTH and between LENGTH and
D1,D2,... If there are no dependencies, there are no characters after LENGTH.
If there are any contradictions in the String[], the method returns -1. There
is a contradiction if:
*there is no way to order the tasks such that all dependencies are resolved.
*dependency lists refers to jobs that are not defined (don't have their own
element) in the String[].
*the tasks are not uniquely named - more than one element in the String[] has
the same TASKNAME.
The method signature is:
public int takeOverTime(String[] tasks);
tasks is an String[] of elements defining between 1 and 20 tasks, inclusive.
Elements in the String[] are of the syntax described above(TopCoder will check
this).
Examples:
If the String[] is:
{"KILLPEOPLE 50",
"BUILDHOUSES 10 LAND",
"LAND 2 KILLPEOPLE",
"CLEANUPBODIES 5 KILLPEOPLE,LAND",
"PLANTNEWLAWN 10 CLEANUPBODIES,LAND"}
First KILLPEOPLE must be done, then LAND, then BUILDHOUSES and CLEANUPBODIES
can be worked on simultaneously. When CLEANUPBODIES is done, PLANTNEWLAWN can
start (BUILDHOUSES will still be going on).
At Time=0, KILLPEOPLE starts.
At Time=50, KILLPEOPLE is done and LAND starts.
At Time=52, LAND is done and CLEANUPBODIES and BUILDHOUSES starts.
At Time=57, CLEANUPBODIES is done and PLANTNEWLAWN starts.
At Time=62, BUILDHOUSES is done.
At Time=67, PLANTNEWLAWN is done.
The method returns the time for everything to be completed: 67. |