Job Scheduling Algorithm

Question

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

Given N tasks, and the dependencies among them, please provide an execution sequence, which make sure jobs are executed without violating the dependency.

Sample File:

5

1<4

3<2

4<5

First line is the number of total tasks. 1<4 means Task 1 has to be executed before task 4.

One possible sequence would be: 1 4 5 3 2

My solution uses a DAG to store all the numbers, followed by a topological sort. Is there a less heavy-handed way of solving 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 said by several users (Gassa, shekhar suman, mhum and Colonel Panic) the problem is solved by finding a topological sorting. As long as the iterator in dag returns the elements in that order it's correct. I don't where the DirectedAcyclicGraph class is from, so I can't help with that. Otherwise, this method does the parsing as yours and uses a simple algorithm (actually, the first one springing 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's 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;
}

BTW, in your hm array initialization you define it has having 6 elements. It leaves the 0 position null (not a problem since you don't call it anyway) but in the general case the number of tasks could be greater than 5 and then you'll have and IndexOutOfBoundsException

Another punctilious remark, when adding the edges, in case of circular dependencies, if the message of the Exception raised by DAG is not clear enough, the user could be confused. Again, since I don't know where that class is from, I can't know.