Number of days to install n programs

Revision en2, by OneWhoKnocks, 2020-02-23 21:04:28

Rick is planning to install n programs on his computer. He has to figure out how many days will it take for him to install n programs. There are a couple of things though which he has to keep in mind:

a) A program can be dependent on other program(s) — it means if program B is dependent on program A. A will have to be installed any day before B will be installed.

b) He can install at most k programs in a day.

We will be given the dependency relationship between the programs. Eg:

n : 6, K : 2

1 -> 5,6

2 -> 5,6

3 -> 4

4 -> 5,6

It will take Rick 3 days to install all the programs ->

(1st day: 1,3) (2nd Day: 2,4) (3rd Day: 5,6)

I thought of converting the above problem to a graph and then use topological sorting. But i am not able to come up with the whole solution to this problem.

Can anyone help me with this? Thanks.

Tags #graph, topological sort, #bfs, #queue

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English OneWhoKnocks 2020-02-23 21:04:28 42
en1 English OneWhoKnocks 2020-02-23 21:02:52 912 Initial revision (published)