I came across this problem in real life and thought it could be made into an interesting puzzle. I will enjoy seeing how my eventual solution could be improved!
Here's the situation.
- There are 290 themes that need to be discussed.
- Each theme requires discussion by some subset of 22 people.
- We need to schedule an efficient number of meetings so that:
- All themes get discussed once
- All the people who are impacted by the theme are in the discussion.
It would, of course, be possible to have 290 meetings with just the subset of people who are needed.
On the other extreme, we could get all 22 people together and have one giant meeting.
The themes will be quite quick to discuss (say 10 minutes), but we don't want to waste people's time sitting in meetings where many of the themes do not impact them.
So the plan will be to have a number of meetings with different subsets of the people and cover all the themes.
Part of the puzzle is to think about what efficient means here in real life terms. So if you have some ideas to improve the scoring then you can include that and I may update the scoring system in response. There's a qualitative aspect to this where neither of the two extremes above is satisfactory.
But for the sake of scoring, here's how we will do it:
- Convening a meeting wastes 15 minutes of time per participant
- Being in a meeting wastes 10 minutes per theme for each participant who is not involved with the theme
- A meeting wastes 5 minutes per participant every 10 themes (coffee break)
So we want to minimize the waste.
By my reckoning:
- One big meeting of everyone wastes 55,180 minutes
- 290 separate meetings wastes 13,620 minutes
- The solution I found wastes 9,530 minutes
I calculated this with a python script. With one big meeting we have:
- 21 participants are required (I should have realized that person R doesn't meet anyone) and we are going to go through all 290 themes.
- The meeting wastes 15 mins * 21 people = 315 mins to convene (scoring rule 1)
- The first theme (1516) only engages 4 people (B, M, P, and T). So the other 17 people are wasting ten minutes each. So add 10 mins * 17 people = 170 mins to the waste (scoring rule 2)
- This will have to be repeated for the other 289 ideas. This is easy to calculate. There are 908 people themes (sum of the 1s in the below database), so it's (21 people * 290 themes)-908 involved people = 5182 uninvolved people. So total waste from scoring rule 2 is 51,820
- After 10 themes, 5 mins * 21 people are wasted, so over the course of the whole meeting there will be 29 such breaks which will waste 5 min * 21 people * 29 breaks = 3045 mins (scoring rule 3)
- So the total waste is 55,180mins
If we have 290 meetings with just the right people:
- It wastes 908 * 15 mins = 13,620 mins (scoring rule 1) to convene the meetings
- No time is wasted in the meetings (scoring rule 2)
- No meetings have more than 10 themes (scoring rule 3)
- Total waste: 13,620 mins
The themes are listed below along with the participants.
And in a .CSV format:
Theme,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V
1516,,1,,,,,,,,,,,1,,,1,,,,1,,
2339,,1,,,,1,,,,,,1,,,,,,,1,,1,
4134,1,1,,,,1,,1,,,,,,1,,,,,,,,
1567,,,,,,,,,,,1,1,,,,,,,1,1,1,
1526,1,,,,,,1,,,,,,1,,,1,,,,,,1
3718,1,,,,1,,1,,,,,,,,,,,,1,,,1
2791,1,,,,1,1,1,,,,,1,,,,,,,,,,
574,,,,,,1,1,1,,1,,1,,,,,,,,,,
1627,1,1,,1,1,,,,,,1,,,,,,,,,1,,
3246,,,,,,,,,,,1,1,1,,1,1,,,,1,,
3120,1,1,1,,,,,,,,1,,,,,,,,1,,1,
3893,,,1,1,1,,,1,,,1,1,,,,1,,,,,,
3265,,,1,,,,,1,,,1,1,1,,,1,,,,1,,
363,1,1,1,,,1,,,,,1,,,,,,,,1,,1,
1709,1,,,,,,1,1,,,,,1,,,,,,1,,1,1
3500,,,1,1,1,,1,1,,,1,,,,,1,,,,,,
3125,,,1,,,,1,1,,,1,1,1,,1,,,,,1,,
3428,1,1,1,,,,1,1,,,,,1,,1,,,,1,1,,
244,1,1,,,1,,,,,,1,1,1,,,1,,,1,1,,
2448,1,1,1,,,,,1,,,1,1,1,,,1,,,,1,,
3434,,,,,,,1,,,,,,,,,,,,,,1,1
1240,,1,,1,,,,,,,,,,,1,,,,,,,
476,,,,,,,,,,,,1,,,,,,,,1,1,1
3025,1,,,,,,,,,,1,,1,,,,,,,,1,
442,,1,,,,1,,,,,,,1,,,,,,1,,,
3400,1,1,,,,,,,,,1,1,,,,,,,,,1,
371,1,,,,,,1,1,,,,,,,1,,,,,,,1
1939,1,,,,,,1,1,,,,,1,,,,,,,,,1
4241,,,,,,,,,,,,,,,,,1,,1,,,
971,,,,,,,,,,,,,,,,,1,,,,1,
1117,,,,,,,,,,1,,,1,,,,,,,,,
258,,,,,,,,,,1,,,,1,,,,,,,,
611,,,,,,,1,,,,,1,,,,,,,,,,1
1703,,,,1,,,1,,,,1,,,,,,,,,,,
2136,,,,1,1,,,1,,,,,,,,,,,,,,
3307,,,,,,,,,,,1,,,,1,1,,,,,,
879,,1,,,,1,,,,,,,,,,,,,1,,1,
3404,,,,,,,1,,,,1,1,,,,,,,,,,1
1737,1,,1,,1,,,,1,,,,,,,,,,,,,
1736,1,,1,,1,,,,1,,,,,,,,,,,,,
1768,1,,,,1,,1,,,,,,1,,,,,,,,,
1447,,,,,,,,,,1,1,1,,,1,,,,,,,
3843,1,,,1,1,,1,,,,,,1,,,,,,,,,
3890,,,,1,1,,,,,,,,1,,,,,,,,,
3435,,,,1,1,,,,,,,,,,,1,,,,,,
956,,,,1,,,,,,,,1,1,1,,,,,,,,
1491,,,,1,1,1,1,,,,,1,1,1,,1,,,,,,
2216,,1,,,1,,,,,,,,,,,,,,,1,,
500,1,,,,1,,,,,,,,1,,,,,,,,,
962,1,,1,,1,,,1,,,1,,,,,,,,,,,
3308,1,1,1,,1,,,1,,,1,1,,,1,,,,,1,,
3218,1,1,1,,1,,,1,,,1,1,1,,1,,,,,1,,
4245,,,1,,,,,1,,,,,,,,,,,,,,
1759,,1,,,,,,,,,,,1,,,,,,,,1,
3999,1,,,,,,,,,,,,,,1,,,,,,1,
3934,,,,,1,,,,,,,,,,,,,,1,,1,
3624,,,,,,,,,,,1,1,,,1,,,,,1,,
2376,1,1,,,,,,,,,,,,,1,,,,,,1,
2866,,,,,1,,,,,,,,,,,,,,1,1,1,
33,,,,1,1,,,,,,1,1,,,,,,,,,,
3432,1,1,,,,,,,,,,1,1,,,,,,,1,,
985,1,,1,1,1,,,,,,1,,,,,,,,,,,
3176,1,,,1,1,,,,,,1,,,,,1,,,,,,
647,,,1,1,1,,,,,,1,1,,,,1,,,,,,
497,,,1,1,1,,,,,,1,1,,,,1,,,,,,
818,1,,1,1,1,,,,,,1,1,,,,1,,,,,,
2731,1,1,1,,,,,,,,1,1,1,,1,,,,,1,,
3374,1,1,1,,,,,1,,,1,1,1,,1,,,,,1,,
3429,1,1,,,1,,,,,,,,1,,1,,,,1,1,1,1
2218,1,1,1,,,,,1,,,1,1,1,,1,,,,1,1,,
3841,,,,,,,,,,,,,1,,,,,,,,,
1694,,,,,,,1,1,,,,,,,,,,,,,,
3342,,,,,,,1,1,,,,,,,,,,,,,,
3966,,,,,,,1,1,,,,,,,,,,,,,,
2670,,,,,,,1,1,,,,,,,,,,,,,,
3655,,,,,,,1,1,,,,,,,,,,,,,,
3967,,,,,,,1,1,,,,,,,,,,,,,,
92,1,,,,,,,1,,,,,,,,,,,,,,
3192,1,,,,,,,1,,,,,,,,,,,,,,
2514,,,,1,,,,,,,,,,,,1,,,,,,
137,,,,1,,,,,,,,,,,,1,,,,,,
138,,,,1,,,,,,,,,,,,1,,,,,,
147,,,,1,,,,,,,,,,,,1,,,,,,
3223,,,1,,,,,,,,,,,,,1,,,,,,
3443,,,1,,,,,,,,,,,,,1,,,,,,
996,,,1,1,,,,,,,,,,,,,,,,,,
3469,,,1,1,,,,,,,,,,,,,,,,,,
1087,1,,,,,,,,,,,,,,,,,,1,,,
915,1,,,,,,,,,,,,,,,,,,1,,,
2798,1,,,,,,,,,,,,,,,,,,1,,,
2369,1,1,,,,,,,,,,,,,,,,,,,,
2805,1,,,,,1,,,,,,,,,,,,,,,,
1661,1,,,,,1,,,,,,,,,,,,,,,,
2785,1,,,,,1,,,,,,,,,,,,,,,,
3001,1,,,,,,,,,,,,1,,,,,,,,,
3727,1,,,,,,,,,,,,1,,,,,,,,,
2103,,1,,,,1,,,,,,,,,,,,,,,,
2368,,1,,,,1,,,,,,,,,,,,,,,,
3831,,,,,,1,,,,,,,,,,,,,,,1,
2533,,,,1,1,,,,,,,,,,,,,,,,,
2449,,,,1,1,,,,,,,,,,,,,,,,,
2202,,,,,1,,,,,,1,,,,,,,,,,,
1730,,,,,1,,,,1,,,,,,,,,,,,,
1731,,,,1,,,,,1,,,,,,,,,,,,,
1738,,,,1,,,,,1,,,,,,,,,,,,,
1125,,,1,,1,,,,,,,,,,,,,,,,,
2236,,,,1,,,,1,,,,,,,,,,,,,,
2889,,,,1,,,,1,,,,,,,,,,,,,,
3659,,,,1,,,,1,,,,,,,,,,,,,,
3636,,,,,,,,1,,,,,,,,1,,,,,,
3657,,,,,,,,1,,,,,,,,1,,,,,,
718,,,,,,,,,,,1,,,,,1,,,,,,
1701,,,,,1,,1,,,,,,,,,,,,,,,
1697,,,,,1,,1,,,,,,,,,,,,,,,
1691,,,,,,,1,,,,,,1,,,,,,,,,
3163,,,,,,,1,,,,,,1,,,,,,,,,
3224,,,,,,,1,,,,,,,1,,,,,,,,
3272,,,,,,,1,,,,,,,1,,,,,,,,
3319,,,,,,,,,,,,,1,1,,,,,,,,
576,,,,,,,,1,,,,,1,,,,,,,,,
1900,,,,,,,,,,,,,,1,,,1,,,,,
2863,,,,,,,,,,,,,,1,,,1,,,,,
3851,,,,,,,,,,,,,,1,,,1,,,,,
3961,,,,,,,,,,,,,,,,,,,1,,1,
2446,,,,,,,1,,,,,,,,,,,,,,1,
3204,,,,,,,1,,,,,,,,,,,,,,1,
3302,,,,,,,,,,,,,,1,,1,,,,,,
3376,1,1,,,,,,,,,,,,,,,,,1,,,
285,1,1,,,1,,,,,,,,,,,,,,,,,
116,1,,,,1,,,,,,,,,,,,,,1,,,
2433,1,1,,,,,,,,,,,,,,,,,,,1,
307,1,1,,,,,,,,,,,,,,,,,,,1,
2447,1,1,,,,,,,,,,,,,,,,,,,1,
2462,1,1,,,,,,,,,,,,,,,,,,,1,
2480,1,1,,,,,,,,,,,,,,,,,,,1,
2491,1,1,,,,,,,,,,,,,,,,,,,1,
1922,,1,,,,1,,,,,,,,,,,,,,,1,
1298,1,,,,1,,,,,,1,,,,,,,,,,,
1640,,,,1,1,,,,,,1,,,,,,,,,,,
2773,,,,1,1,,,,,,1,,,,,,,,,,,
3041,,,,1,1,,,,,,1,,,,,,,,,,,
2993,1,,,1,1,,,,,,,,,,,,,,,,,
1192,,,1,1,1,,,,,,,,,,,,,,,,,
1734,,,1,1,,,,,1,,,,,,,,,,,,,
1741,,,1,1,,,,,1,,,,,,,,,,,,,
105,,,1,1,,,,,1,,,,,,,,,,,,,
216,,,,1,,,,1,,,1,,,,,,,,,,,
2638,,,,1,,,,1,,,1,,,,,,,,,,,
1880,,,,,,,1,,,,,,1,1,,,,,,,,
1903,,,,,,,1,1,,,,,,,,,1,,,,,
2390,,,,,,,1,1,,,,,,,,,1,,,,,
2913,,,,,,,,,,,,,1,1,,,1,,,,,
3119,1,,,,,,,,,,,1,,,,,,,,,1,
836,,,,,,,,,,,,1,,,,,,,1,,1,
2378,,,,,1,,,,,,1,1,,,,,,,,,,
2199,1,1,,,1,,,,,,,,,,,,,,1,,,
4242,,,,,,,1,1,,,,,,1,,,1,,,,,
2767,1,1,,,,,,,,,,1,,,,,,,,,1,
3014,1,1,,,,,1,,,,,,,,,,,,,,1,
477,1,,,,1,,,,,,1,,,,,1,,,,,,
1350,,,,,,,,,,,1,1,,1,,1,,,,,,
2047,,,,,,,,,,,1,1,,1,,1,,,,,,
3503,,,,,,,,,,,1,1,,1,,1,,,,,,
4207,,,,,,,,,,,1,1,,1,,1,,,,,,
303,1,1,,,,,,,,,,1,,,,,,,1,,1,
318,,,,,1,,,,,,1,1,,1,,1,,,,,,
475,,,,,,,,,,,,1,,,,,,,,,,
2600,,,,,,,,,,,,1,,,,,,,,,,
4159,,,,,,,,,,,,1,,,,,,,,,,
4195,,,,,,,,,,,,1,,,,,,,,,,
2201,,,,,1,,,,,,,1,,,,,,,,,,
454,,,,,1,,,,,,,1,,,,,,,,,,
1025,,,,,1,,,,,,,1,,,,,,,,,,
1302,,,,,1,,,,,,,1,,,,,,,,,,
4346,,,,,1,,,,,,,1,,,,,,,,,,
485,,,,,,,,,,,1,1,,,,,,,,,,
589,,,,,,,,,,,1,1,,,,,,,,,,
681,,,,,,,,,,,1,1,,,,,,,,,,
2513,,,,,,,,,,,1,1,,,,,,,,,,
316,,,,,,,,,,,1,1,,,,,,,,,,
3066,,,,,,,,,,,1,1,,,,,,,,,,
2792,1,,,,,,,,,,,1,,,,,,,,,,
3191,1,,,,,,,,,,,1,,,,,,,,,,
3506,1,,,,,,,,,,1,,,,,,,,,,,
1245,,,,,,,,,,1,1,,,,,,,,,,,
1121,,,1,,,,,,,,,1,,,,,,,,,,
3219,,1,,,,,,,,,,1,,,,,,,,,1,
284,,,,,,,,,,1,1,1,,,,,,,,,,
295,,,,,,,,,,1,1,1,,,,,,,,,,
1242,,,,,,,,,,1,1,1,,,,,,,,,,
1439,,,,,,,,,,1,1,1,,,,,,,,,,
721,,,,,,,,,,,1,1,,,,1,,,,,,
1160,,,1,,,,,,,,1,,,,,1,,,,,,
289,,,1,,,,,,,,1,,,,,1,,,,,,
3466,,,1,,,,,,,,1,,,,,1,,,,,,
1128,,,,1,,,,,,,1,1,,,,,,,,,,
2763,,1,,,,,,,,,1,1,,,,,,,,,1,
3095,,1,,,,,,,,,1,1,,,,,,,,,1,
3096,,1,,,,,,,,,1,1,,,,,,,,,1,
2946,,,1,1,,,,,,,1,,,,,1,,,,,,
2947,,,1,1,,,,,,,1,,,,,1,,,,,,
2949,,,1,1,,,,,,,1,,,,,1,,,,,,
1693,,,,,,,1,,,,,1,,,,,,,,,,
1878,,,,,,,1,,,,,1,,,,,,,,,,
3704,,,,,,,1,,,,,1,,,,,,,,,,
3830,,,,,,,1,,,,,1,,,,,,,,,,
4243,,,,,,,1,,,,,1,,,,,,,,,,
1294,,,,,,,,,,1,,1,,,,,,,,,,
2741,,,,,,,,,,1,,1,,,,,,,,,,
2855,,,,,,,,,,1,,1,,,,,,,,,,
3142,,,,,,,,,,1,,1,,,,,,,,,,
3809,,,,,,,,,,1,,1,,,,,,,,,,
359,1,,,,,,,,,,,,,,,,,,,,,1
1030,1,,,,,,,,,,,,,,,,,,1,,,1
1717,1,,,,,,,,,,,,,,,,,,1,,,1
3000,1,,,,,,1,,,,,,,,,,,,,,,1
2062,1,,,,,,1,,,,,,,,,,,,,,,1
3359,1,,,,,,1,,,,,,,,,,,,1,,,1
746,1,,,,,,1,,,,,,,,,,,,1,,,1
1379,1,,,,,,1,,,,,,,,,,,,1,,,1
3360,1,,,,,,1,,,,,,,,,,,,1,,,1
4036,1,,,,,,1,,,,,,,,,,,,1,,,1
1474,,,,,1,,,,,,,,,,,,,,,,,
730,1,,,,,,,,,,,,,,,,,,,,,
141,1,,,,,,,,,,,,,,,,,,,,,
1542,1,,,,,,,,,,,,,,,,,,,,,
1662,1,,,,,,,,,,,,,,,,,,,,,
1747,1,,,,,,,,,,,,,,,,,,,,,
2171,1,,,,,,,,,,,,,,,,,,,,,
115,1,,,,1,,,,,,,,,,,,,,,,,
3129,1,,,,1,,,,,,,,,,,,,,,,,
3274,1,,,,1,,,,,,,,,,,,,,,,,
1368,1,,,,1,,,,,,,,,,,,,,,,,
58,,,,1,,,1,,,,,,,,,,,,,,,
35,,,,1,,,1,,,,,,,,,,,,,,,
38,,,,1,,,1,,,,,,,,,,,,,,,
39,,,,1,,,1,,,,,,,,,,,,,,,
47,,,,1,,,1,,,,,,,,,,,,,,,
49,,,,1,,,1,,,,,,,,,,,,,,,
62,,,,1,,,1,,,,,,,,,,,,,,,
68,,,,1,,,1,,,,,,,,,,,,,,,
73,,,,1,,,1,,,,,,,,,,,,,,,
91,,,,1,,,1,,,,,,,,,,,,,,,
93,,,,1,,,1,,,,,,,,,,,,,,,
3169,,,,1,,,1,,,,,,,,,,,,,,,
631,,,,,,,1,,,,,,,,,,,,,,,1
1710,,,,,,,,1,,,,,,,,,,,,,,1
2312,,,,,,,1,,,,,,,,,,,,,,,1
2313,,,,,,,1,,,,,,,,,,,,,,,1
4052,,,,,,,1,,,,,,,,,,,,,,,1
2980,,,,,,,,1,,,,,,,,,,,,,,1
2982,,,,,,,,1,,,,,,,,,,,,,,1
4305,,,,,,,,1,,,,,,,,,,,,,,1
761,,,,,,,1,1,,,,,,,,,,,,,,1
824,,,,,,,1,1,,,,,,,,,,,,,,1
1532,,,,,,,1,1,,,,,,,,,,,,,,1
1942,,,,,,,1,1,,,,,,,,,,,,,,1
3239,,,,,,,,1,,,,,,,,,,,1,,,1
3877,1,,,,,,1,1,,,,,,,,,,,,,,1
791,1,,,,,,,1,,,,,,,,,,,1,,,1
832,1,,,,,,,1,,,,,,,,,,,1,,,1
1976,1,,,,,,1,1,,,,,,,,,,,,,,1
2067,1,,,,,,,1,,,,,,,,,,,1,,,1
3231,1,,,,,,1,1,,,,,,,,,,,,,,1
3338,1,,,,,,1,1,,,,,,,,,,,,,,1
770,1,,,,,,1,1,,,,,,,,,,,1,,,1
792,1,,,,,,1,1,,,,,,,,,,,1,,,1
71,1,,,,,,1,1,,,,,,,,,,,1,,,1
844,1,,,,,,1,1,,,,,,,,,,,1,,,1
1530,1,,,,,,1,1,,,,,,,,,,,1,,,1
2060,1,,,,,,1,1,,,,,,,,,,,1,,,1
3394,1,,,,,,1,1,,,,,,,,,,,1,,,1
1050,,,,,,,,,,,1,,,,,,,,,,,
3591,,,,,,,,,,,1,,,,,,,,,,,
2536,,,1,,,,,,,,1,,,,,,,,,,,
3020,,,1,,,,,,,,1,,,,,,,,,,,
3182,,,1,,,,,,,,1,,,,,,,,,,,
3183,,,1,,,,,,,,1,,,,,,,,,,,
3553,,,1,,,,,,,,1,,,,,,,,,,,
3564,,,1,,,,,,,,1,,,,,,,,,,,
3629,,,1,,,,,,,,1,,,,,,,,,,,
4082,,,1,,,,,,,,1,,,,,,,,,,,
3,,,1,,,,,,,,1,,,,,,,,,,,
676,,,1,,,,,,,,1,,,,,,,,,,,
698,,,1,,,,,,,,1,,,,,,,,,,,
909,,,1,,,,,,,,1,,,,,,,,,,,
1926,,,1,,,,,,,,1,,,,,,,,,,,
1499,,,1,,,,,,,,1,,,,,,,,,,,
2912,,,1,,,,,,,,1,,,,,,,,,,,
3453,,,1,,,,,,,,1,,,,,,,,,,,