4
$\begingroup$

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day.

eg - Suppose there are 3 people who are free on (M,T,W,Th,F), (M,W) and (W,Th,F) respectively. They can all be placed in the same group since all of them can meet on Wednesday.

$\endgroup$
  • $\begingroup$ @PålGD Edited and made it simpler. $\endgroup$ – ask Jun 11 '15 at 16:19
  • $\begingroup$ Superpositions are allowed? $\endgroup$ – André Souza Lemos Jun 11 '15 at 16:36
  • 1
    $\begingroup$ It's probably NP-hard. Check out set cover. Or maybe red-blue dominating set on bipartite graphs? With days on one side and people on the other side of the bipartition? $\endgroup$ – Pål GD Jun 11 '15 at 16:36
-1
$\begingroup$

Just model your problem with graph and use any of the widely known search algorithm to help traverse your graph. After doing that, if you have any problem, let us know.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Unfortunately, this answer doesn't have enough detail to be useful. It's not at all obvious to me how to use a search algorithm to do what sounds much more like clustering than traversal. How do you propose to do that? $\endgroup$ – David Richerby Jun 13 '15 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.