A computing company is running a set of processes every day. Each process has it

Question

A computing company is running a set of processes every day. Each process has its own start time and finish time, during which it runs continuously. The company has developed a process_check module, that runs briefly (consider this to take just 1 point in time) and records important pieces of information about the processes running at that time. The company would like to run the process_check module as few times as possible each day, while making sure that the module is called at least once during the execution of each process. Give an efficient algorithm that based on the start and finish time of each process will find the smallest set of possible moments of time at which to run the process_check module (making sure that the module is invoked at least once for each process). Note: to prove that your greedy strategy yields the optimal solution, you have to provet hat the problem has thegreedy-choice property

Explanation / Answer

First of all, let us show that this problem has the greedy choice property.

This means that global optimal solution can be obtained by selecting local optimal solutions. Now observe the following:

Therefore, the problem exhibits greedy choice property. So, we can use a greedy algorithm for this problem.

The greedy step in this algorithm is to delay the process_check as long as possible. So, it must be run towards the end of each process. So the following algorithm can be used:

In the above algorithm, the costliest step is the sorting step. By using an optimal sorting algorithm such as merge sort, we can accomplish it in O(n log n) asymptotic time.

Thus, this greedy algorithm also takes O(n log n) asymptotic time complexity.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.