Task Scheduling Algorithm

Question

Got this question during an interview. I wanted to know if there was a better solution:

Given the N tasks and the dependencies between them, provide a sequence of execution that ensures that tasks are completed without breaking the dependency.

Example file:

5

1 <4

3 <2

4 <5

The first line is the number of jobs. 1 <4 means that task 1 must be performed before task 4.

One sequence is possible: 1 4 5 3 2

My solution uses DAG to store all numbers and then topological sort. Is there a less decisive way to solve this problem?

DirectedAcyclicGraph<Integer, DefaultEdge> dag = new DirectedAcyclicGraph<Integer, DefaultEdge>(DefaultEdge.class); Integer [] hm = new Integer[6]; //Add integer objects to storage array for later edge creation and add vertices to DAG for(int x = 1; x <= numVertices; x++){ Integer newInteger = new Integer(x); hm[x] = newInteger; dag.addVertex(newInteger); } for(int x = 1; x < lines.size()-1; x++){ //Add edges between vertices String[] parts = lines.get(x).split("<"); String firstVertex = parts[0]; String secondVertex = parts[1]; dag.addDagEdge(hm[Integer.valueOf(firstVertex)], hm[Integer.valueOf(secondVertex)]); } //Topological sort Iterator<Integer> itr = dag.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } 

Answer 1

As already mentioned by several users (Gassa, Shekhar Suman, Mkhum and Colonel Panik), the problem is solved by searching for topological sorting. As long as the iterator in dag returns the elements in that order, it is correct. I don't have a DirectedAcyclicGraph class, so I can't help it. Otherwise, this method parses like yours and uses a simple algorithm (in fact, the first one comes to my mind)

 public static int[] orderTasks (String[] lines){ // parse int numTasks = Integer.parseInt(lines[0]); List<int[]> restrictions = new ArrayList<int[]>(lines.length-1); for (int i = 1; i < lines.length; i++){ String[] strings = lines[i].split("<"); restrictions.add(new int[]{Integer.parseInt(strings[0]), Integer.parseInt(strings[1])}); } // ordered int[] tasks = new int[numTasks]; int current = 0; Set<Integer> left = new HashSet<Integer>(numTasks); for (int i = 1; i <= numTasks; i++){ left.add(i); } while (current < tasks.length){ // these numbers can't be written yet Set<Integer> currentIteration = new HashSet<Integer>(left); for (int[] restriction : restrictions){ // the second element has at least the first one as precondition currentIteration.remove(restriction[1]); } if (currentIteration.isEmpty()){ // control for circular dependencies throw new IllegalArgumentException("There circular dependencies"); } for (Integer i : currentIteration){ tasks[current++]=i; } // update tasks left left.removeAll(currentIteration); // update restrictions Iterator<int[]> iterator = restrictions.iterator(); while (iterator.hasNext()){ if (currentIteration.contains(iterator.next()[0])){ iterator.remove(); } } } return tasks; } 

By the way, in your initialization of the hm array, you determine that it has 6 elements. It leaves the zero position 0 (not a problem, since you don't call it at all), but in the general case the number of tasks can be more than 5, and then you will have an IndexOutOfBoundsException

Another noteworthy remark when adding edges in the case of circular dependencies, if the exception message generated by the DAG is not clear enough, the user may be confused. Again, since I do not know where this class comes from, I do not know.