Graph, Scheduler, and Task, with properties given below. Use the class A5 to test your program. This class is available from the CS 146 web site. As always, you may define any additional classes or methods that you find helpful or necessary.
The Graph class is to have a constructor that takes a List of vertex names, an addEdge method, and a topsort method that takes no argument. The constructor is to interpret each of the list elements as a String representing the name of a vertex. Second and subsequent occurrences of the same vertex name in this list should be ignored. The addEdge method is to take two String arguments, interpret them as vertex names, and add an edge to the graph from the first vertex to the second. If either of the arguments is not a vertex name, then it should do nothing.
The topsort method should work as in Weiss, Section 9.2, except that in the case of correct input (with no cycles) it should return a list of the vertex names in topological order. If the input contains a cycle, it should throw an IllegalArgumentException (not a CycleFound exception). The exception object that is thrown, if sent the getMessage message, should return an error message (as a String) stating that a cycle is to be found among an explicitly named collection of vertices (e.g., among v1, v3, and v4 for the graph of Figure 9.12 of the text).
The Scheduler class is to have two public and static methods buildSchedule and getProfit that are related to a scheduling problem involving a collection of tasks, each of which takes 1 unit of time to complete, and each of which has a positive integer profit and a positive integer deadline. The problem is to schedule a subset of the tasks to a processor so that the processor works on at most one task at a time, no task completes after its deadline, and the sum of the profits of the total scheduled tasks is maximized.
The buildSchedule method is to take a linked list of Task objects and return a schedule represented as an ArrayList of tasks, using the following greedy algorithm: consider the items in nondecreasing order of profit. Schedule each item as late as possible consistent with its deadline and with previously scheduled tasks. If there is no time slot consistent with these values, then don't schedule the task at all. Position i of the schedule is to contain the task being scheduled between times i and i+1.
So for example, if for tasks 1 through 10, task i has a deadline of 1 + (i2 mod 10) and a profit of 10*i, then task 10 would go to slot 0, task 9 to slot 1, task 8 to slot 4, task 7 to slot 9, task 6 to slot 6, task 5 to slot 5, task 4 to slot 3 (after checking slots 6, 5, and 4), task 3 to slot 8 (after checking slot 9), and task 2 to slot 2 (after checking slots 4 and 3). Task 1 could not go into slot 1 or 0, so it would not be scheduled.
The getProfit method is to take an ArrayList of tasks, interpret it as a processor schedule and return the total profit. In the example above, the total profit would be 440.
The Task class is to have a constructor with 3 integer arguments providing a task id number, a deadline and a profit. It is to have a toString method that returns a task name based on the id number. You might want to have it implement the Comparable interface, and to provide one or more selectors.
You may, although you needn't, use the techniques of Chapter 8 to avoid the sequential search for slots suggested by the greedy algorithm example above. The idea is that each time slot would be represented by the latest available slot at or before that time slot.