Topology sorting algorithm pen test for priority queue

Over 20 Years Batch Algorithm Written Test Question 3

There are N tasks executed, each taking Pi's time to complete.At the same time, there may be some dependencies between tasks.For example, Task 1 may depend on Task 2 and Task 3. Task 1 must execute both Task 2 and Task 3 before it can execute.

Only one task can be executed at the same time, and the switch cannot be paused to execute other tasks until the task is completed.To enhance the user experience of the platform, you want to minimize the average return time for tasks.The return time of a task is defined as the time the task is completed minus the time the platform receives the task.At zero time, all N tasks have been received by the platform.

Schedule the task execution order to minimize the average return time.

Enter a description:

The first row contains two positive integers, N and M, representing the number of tasks and M task dependencies, respectively.

The second line contains N positive integers, and the number of i (1 <= i <= N) represents the processing time Pi of the ith task.

The next M lines, each representing a task dependency.Each row contains two integers Ai (1 <= Ai <= N), Bi (1 <= Bi <= N).Indicates that the Bi task depends on the Ai task.Data guarantees no circular dependency.

Data Range:

 1 <= N <= 1000

 1 <= M <= 50000

 1 <= Pi <= 10000

Output description:

Output a line containing N integers (separated by a space character) where the i (1 <= i <= N) integer represents the number of the ith task performed by multiple chickens.If there are several possible scenarios, the output dictionary order is the smallest (priority is given to smaller numbered tasks).

Example:

Input:

5 6

1 2 1 1 1

1 2

1 3

1 4

2 5

3 5

4 5

Output:

1 3 4 2 5

Ideas:

If dependencies are not considered, in order to achieve the minimum average return time, the tasks that take less time to execute are executed sooner. With dependencies, we must complete dependent tasks before we can perform dependent tasks. Only the number of dependent tasks is 0 (meaning dependent tasks are completed before we can perform this task)Execution of the transaction), where execution order is still sorted by processing time; use small top heap to store current executable tasks, update the number of dependencies after each heap outflow, and add tasks with 0 dependencies to the priority queue

C++ code:

#include<iostream>
#include<string>
#include <vector>
#include <list>
#include <queue>
#include<algorithm>


using namespace std;

typedef struct Task{
	int seq;    //Task Sequence Number (1,2,3,...,N)
	int time;   //Task processing time
	Task() :seq(0), time(0){}
}Task;

struct cmp{
	bool operator()(const Task &a, const Task &b)
	{
		return a.time != b.time ? a.time > b.time : a.seq > b.seq;  //Minimum output dictionary order (preferring smaller numbered tasks)
		//Return a.time > b.time; //Sort time using a small top heap, first exporting decimals
		//Return a.time < b.time //Sort time using a large top heap, first outputting most of the output
	}
};

int main(void){
	int N, M;
	cin >> N >> M;    //Number of Tasks Input N(1,2,3,...,N) and Number of Task Dependencies
	
	vector<Task> task(N + 1);   //Storage Tasks
	vector<list<int> > Adj(N+1, list<int>());  //Adjacency table
	vector<int> inDegree(N+1, 0);     //Save entry for each node
	
	//Enter processing time for the task
	for (int i = 1; i < N + 1; ++i)
	{
		Task tmp;
		tmp.seq = i;
		cin >> tmp.time;
		task[i] = tmp;
	}
	//Input Task Dependency Establishment Adjacency Matrix
	for (int i = 0; i < M; ++i)
	{
		int u, v;
		cin >> u >> v;
		Adj[u].push_back(v);
		inDegree[v]++;
	}
	//Queue Zero-Entry Tasks
	priority_queue<Task, vector<Task>, cmp> taskque;
	for (int i = 1; i < N + 1; ++i)
	{
		if (inDegree[i] == 0)
			taskque.push(task[i]);
	}
	
	//Sort Topologically
	vector<int> tasksort;
	while (!taskque.empty())
	{
		Task complete = taskque.top();
		taskque.pop();
		list<int>::iterator ite = Adj[complete.seq].begin();
		for (; ite != Adj[complete.seq].end(); ++ite)
		{
			inDegree[*ite]--;
			if (inDegree[*ite] == 0)
				taskque.push(task[*ite]);
		}
		tasksort.push_back(complete.seq);
	}
	//Output Task Order
	for (auto task : tasksort)
	{
		cout << task << " ";
	}
	cout << endl;
	return 0;
}

--------------------------------------------------

Reference Blog:

C++ priority_queue usage (large top heap, small top heap)

Summary of priority_queue usage in STL

Pingduo 2019 Xuebao Batch Written Test

Tags: less

Posted on Sun, 11 Aug 2019 20:05:25 -0700 by Deemo