For each student, form a bitstring of all the students whose shifts overlap this student's shift. Find the minimum number of such bitstrings needed such that their bitwise-or has all ones.
You can then use a breadth-first search to determine the smallest subset. Try all combinations of one bitstring, then all combinations of two, then four, then eight. After you find one, keep going until you've found all working combinations of the same length. For each of these, perform the same power-of-two breadth-first search to determine the maximum number of elements you can remove from each subset. When you overreach, back off in powers of two. Repeat this back-and-forth, dropping subsets that fall behind, until you find the best subset or set of subsets. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
