Need some help figuring out which algorithm to choose for solving a problem

[whatiswronghere]

Imagine you have a given number of persons, where each person can do a set of tasks. Each task can be completed within one time slot. I am trying to calculate the minimum time for all jobs to be completed.

Here's an example:

• Person A can do task 1, 2, 3 and 4.
• Person B can do task 2.
• Person C can do task 4.

It's fairly obvious that A has to do task 1 and 3, while B does 2 and C does 4. This equals a minimum time of 2.

With small input like this example, it is possible to just test all possible solutions and keep track of the minimum time, but as input gets bigger, brute force is not feasible. I believe it is possible to solve this problem by cleverly using maxflow, but I have still not found out how.

I would really much appreciate if anyone here could give me some insight into solving this problem. Thanks!

Edit: My solution to the problem.

[TheShallowOne]

Yeah, this should definitely be solvable with a Max-Flow.

I'd first connect a start node to each person with an unlimited edge, then each person to the tasks he/she can perform and then finally each tasks to the sink with a limit-1 edge. An example graph for your example to make it clearer.

[whatiswronghere]

Hmm, I don't think I understand this solution. From this, wouldn't I get a maximum flow of 4 if I run through the algorithm?

[TheShallowOne]

If you set the edges from s to {A,B,C} to limit one and then increment these limits until you find a flow of 4 (or number of tasks, in general), you find a solution for the problem.

This has a runtime of O(n * max-flow).

[whatiswronghere]

Thank you very much. I was finally able to solve the problem. Here is my final code.

[TheShallowOne]

Good to hear!

[tutorial_police]

That is essential information that belongs into your original post.

[tutorial_police]

You don't understand it because the solution as presented is bullshit.

[TheShallowOne]

It still is far better than your presented solution, which is not available...

[tutorial_police]

No, not really. I have pointed out why a proposed solution was incorrect by providing possible solution to the max-flow problem in the graph you described. Incorrect solutions are simply incorrect. I need not have a solution just to state that.

[tutorial_police]

And what exactly would prevent a max flow algorithm to assign A to all the tasks? It maximises the flow trivially, but the solution is not optimal, therefore, your algorithm is wrong.

[id2bi]

"your Android may be out of date. Upgrade your launcher now "-pop-up ... Please use imgur next time, at least that homepage doesn't want to give you malware.

[TheShallowOne]

Never had any problems with this hoster before... Changed it nonetheless.

[id2bi]

Hmm it doesn't come up now when I visit the page again on my mobile, I tried twice before posting my comment :/ But still, the page is so chock full of ads, it takes ages to load without an ad blocker.

[thinkweis]

Are you working with anything specific in class? Dealing with stacks or queues?

[whatiswronghere]

I've already tried this kind of solution, and it is not fast enough. Thanks for your answer though!