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());
    }

This problem is the classic motivation for doing topological sort, so perhaps the answer is "no" unless there are additional constraints. — Gassa
– Gassa, Commented Dec 19, 2014 at 19:56
@Gassa-Topological sorting has to be involved in it because dependencies have to be satisfied for each process! Right now, I cant think one. — Am_I_Helpful
– Am_I_Helpful, Commented Dec 19, 2014 at 20:00
You've already determined that the output of a topological sort provides a solution. Conversely, observe that any solution to this problem would be a valid output for a topological sort. Thus, this problem is equivalent to topological sort. — mhum
– mhum, Commented Dec 19, 2014 at 20:47
"The dependencies form a directed acyclic graph. A feasible schedule is a topological sort." is the correct answer, as you wrote. In an interview you might like to explain a particular algorithm (while noting there's one in the standard library). You could draw a picture and solve a small example. — Colonel Panic
– Colonel Panic, Commented Dec 23, 2014 at 11:39

dtortola · Accepted Answer · 2014-12-26 09:24:15Z

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.

Collectives™ on Stack Overflow

Job Scheduling Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related