#StackBounty: #code-challenge #fastest-algorithm Meeting splitter

Bounty: 50


Large meetings waste working time. Our aim is to split a large meeting into a number of smaller meetings, so the average number topics that a person discusses is minimized but every person has to be in every meeting they are interested in.


Given is a function from a set of topics T to a set of persons P that are interested in this topic $$f:T rightarrow 2^P$$ and maximum partition size m.

This is encoded as an array of arrays, where element f[i] contains the topics of person i.

Test Case

m = 3
f = [


Find a partition of T (a split into subsets that are disjoint and that cover the whole set) into $$X = {T_1, T_2, ldots, T_n}$$ where n<=m, so that the following term is minimized:
$$r = sum_{T’ in X}{(|(bigcup_{t in T’} f(t))|times |T’|)} $$

To help understand r, if each topic takes an hour to discuss, then r is the total amount of person hours required for the meetings.

If there are multiple partition sizes with the same r, n should be minimized as well.

The output should contain the partition X as a two-dimensional array, such as:
$$X = [[0,1,2,3],[4,5,6],[7,8,9]] $$

Winning Condition

I am looking for the fastest algorithm that finds the absolute minimum r and n.

If that is not possible in polynomial time, then I am also looking for an polynomial algorithm that has the lowest upper bound on r in relation to the absolute minimum r (e.g. double).

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.