1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Readme [11.4K]
3 years ago
11

A computing company is running a set of processes every day. Each process has its own start time and finish time, during which i

t 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.
Required:

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).
Computers and Technology
1 answer:
Helga [31]3 years ago
5 0

Answer:

Above all else, let us show that this issue has the greedy choice property.

This implies that worldwide ideal arrangement can be gotten by choosing local ideal arrangements. Presently notice the following:

The global optimal solution of the issue requests us to track down the minimum number of times process_check module should be run.

It is likewise referenced that during each running interaction, process_check module should be called atleast once. Along these lines, the minimum possible number of process_check calls happens when process_check is made close to the quantity of the processes that are run.

Along these lines, we see that the global optimal solution is shaped by choosing optimal answer for the nearby advances.

Along these lines, the issue shows greedy choice property. Thus, we can utilize a greedy algorithm for this issue.

The greedy step in this calculation is to postpone the process_check as far as might be feasible. Thus, it should be run towards the finish of each interaction. So the following algorithm can be utilized:

Sort the cycles by utilizing the completion times.

Towards the finish of the 1st process in the arranged list, run the process_check module. Right now any process that is now running is removed the arranged rundown. The main interaction is additionally removed from the sorted list.

Now repeat stage 2, till all processes are finished.

In the above mentioned algorithm, the costliest advance is the step of sorting. By utilizing the optimal sorting algorithm, for example, merge sort, we can achieve it in O(n log n) asymptotic time.

Along these lines, this greedy algorithm additionally takes O(n log n) asymptotic time complexity.

You might be interested in
What are the answers to everfi
FinnZ [79.3K]
FutureSmart focuses on the important Middle School years by empowering students to become the stewards of their financial futures. This three hour web-based resource educates students on the practicalities of daily financial decisions and the payoffs of long-term planning. Since Middle School is an important period for positive habits
to take form and grow, this course is particularly meaningful.
Through a compelling narrative in which students play the Mayor of a town, local citizens are helped with real-life decisions. From weighing opportunity costs, to delaying instant gratification for long- term gain, students face important questions on their way to becoming FutureSmart. At the end of the course, students compose their own blueprint for the future. FutureSmart c
6 0
3 years ago
For the past five days, the Howard family has traveled these miles: 389;126;419;93; and 394. Find the range and how. Show all yo
Fofino [41]
The answer is 326.

Range is found by subtracting the smallest number in the data set from the largest number.

Highest number: 419
Lowest number: 93

419-93
=326

(Next time make sure to post this under the Mathematics section.)
5 0
3 years ago
What's the component of the hardware?​
melisa1 [442]
Some component of the hardware are central processing unit (CPU), monitor, mouse, keyboard, computer data storage, graphics card, sound card, speakers and motherboard.

I’m sure theirs more but here’s so. Hope this helps!
7 0
2 years ago
Read 2 more answers
An item that appears in a program's graphical user interface is known as a _______.
nydimaria [60]
Widget is an item that appears in a programs graphical user interface.
7 0
3 years ago
Advantages of desktop publishing over traditional methods include       
Licemer1 [7]
From what my teacher taught us it would be c.
6 0
3 years ago
Other questions:
  • Suppose you are using a Mac to read your e-mail messages, and you receive an
    8·2 answers
  • Image files are grouped into two categories: _____.
    5·1 answer
  • Whenever Jim starts his laptop, he sees some commands and numbers appearing on his screen. These instructions are being processe
    12·2 answers
  • Assume we perform a known-plaintext attack against DES with one pair of plaintext and ciphertext. How many keys do we have to te
    14·1 answer
  • the mail merge feature can be used to address the same letter to several different people , true or false
    13·2 answers
  • If you wish to sign out of your Microsoft account, tap or click ____ on the ribbon to open the Backstage view and then tap or cl
    10·1 answer
  • You can get context-sensitive help information from the Code Editor by_________.A) selecting Contents from the Help menu
    9·1 answer
  • which of these tools stick to the edge of an image, thus making it easy to select the shape of an image
    6·1 answer
  • Which of the following is the term for a device (usually external to a computer) that is plugged into a computer's communication
    7·1 answer
  • If you want to stop a loop before it goes through all of its iterations, the break statement may be used. Group of answer choice
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!