+3

How to sort through and respond to a list of random instructions

So I have a homework problem. Let's say that there's a list of 7 tasks to complete, and you have to do them in a specific order. For example you have to do task 4 before you do task 2. But if some tasks' order aren't specified, then you can have to do them in the order of first to last task. For example if I say to do task 4 before 3, and task 7 before 3, then you have to do these tasks in order: 1, 2, 4, 7, 3, 5, and 6 (smaller number comes first, that's why task 4 is before task 7). Notice how the tasks 1, 2, 3, 5, and 6 haven't moved since I never specified them to do so. Oh, and there can as many tasks as possible, but if 2 tasks contradict each other, then the program will simply output "Cannot complete tasks". -------------------------------------------------------------------------------------------------------------- Example Input (one instruction takes up two lines): 6 2 5 4 3 2 Example Output: 1 6 3 2 5 4 7 Explanation of Output: We start with our tasks: 1 2 3 4 5 6 7 6 must come before 2: 1 6 2 3 4 5 7 5 must come before 4: 1 6 2 3 5 4 7 3 must come before 2: 1 6 3 2 5 4 7 Note: Move the tasks as little as possible, so if task 7 comes before task 5, then it should look like this: 1 2 3 4 7 5 6 But not something like this: 1 7 2 3 4 5 6 -------------------------------------------------------------------------------------------------------------- So normally when it comes to a question, I can generally wrap my head around a way of solving it. But I'm completely stumped on this on. I heard from a hint that it uses something to do with DAG's, but I'm unfamiliar with those, and I don't even know where to start. Any help would be appreciated.

8/25/2019 12:33:48 AM

Fuzzy Squid

1 Answer

New Answer

+4

This is the algorithm I'd use. It doesn't check for contradictions as I haven't found an optimal way of doing so. 1. Let n be the number of tasks. Create a list from 1 to n. 2. Iterate over each pair of instructions (e.g., (6, 2), (2, 5), (5, 4)) and do the following: 2.1. Let i,j be the indeces of each element of the pair. For example: List: [1, 2, 3, 4, 5, 6, 7] Pair: (6, 2) Indeces: (5, 1) # 0 based 2.2. If i<j skip to the next pair. Otherwise, place the first element at index j (i.e., before the second element) and continue with the next pair. For example: Old list: [1, 2, 3, 4, 5, 6, 7] New list: [1, 6, 2, 3, 4, 5, 7] 3. Print the list.