You are not logged in. Please login at to post your questions!


Help me with this graph problem

Someone mentioned in an answer that the following problem can be solved using only DFS/BFS:

I am not getting any idea on how to solve this problem without using Dijkstra's algo/ MST. Binary Search is another approach. Can anyone tell how to solve this using only BFS/DFS?

asked 31 Dec '14, 21:54

ketanhwr's gravatar image

accept rate: 15%

Okay, I took a quick look. If there are any errors, I'll fix them as soon as I wake up:

(Presuming different chefs can cook simultaneously.)

You've to pick P Pratas. Each time you're assigning a Prata to a chef, you pick the chef which gives the next Prata earliest. Don't view time as same for all, but store the internal time t of each chef, along with the time r to make their next Prata. With that notation, each iteration, you pick the chef with smallest value of t + r to make a Prata. Their own internal time then becomes t = t + r, and the time to make their next Prata becomes r = r + R. The maximum value of t + r that you picked becomes your answer.

I don't know why you ask for "only BFS/DFS" if you can find an efficient solution elsewhere.

EDIT: Struck me as soon as I pressed submit, and then I also found this on the main discussion channel. The solution removes the ln(L) factor from my solution (assuming priority queue is used with mine). It's practically the same thing with the ranks coalesced together.

Hope that helps. Cheers!


answered 01 Jan '15, 00:25

idraumr's gravatar image

accept rate: 45%

edited 01 Jan '15, 00:37

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 31 Dec '14, 21:54

question was seen: 743 times

last updated: 01 Jan '15, 00:37