1
$\begingroup$

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:

  1. Convening a meeting wastes 15 minutes of time per participant
  2. Being in a meeting wastes 10 minutes per theme for each participant who is not involved with the theme
  3. 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.

enter image description here

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,,,,,,,,,,,
$\endgroup$
  • $\begingroup$ @Oray, I've added a detailed calculation. Hopefully, it is a little clearer. The essence of the problem is not complicated, but it's a little difficult to explain clearly. Let me know if it's clear or not. This problem would suit you! $\endgroup$ – Dr Xorile Feb 27 '18 at 18:13
  • 1
    $\begingroup$ I think it is clear to me, i just want to understand why there is theme with only one person involved.. $\endgroup$ – Untitpoi Feb 28 '18 at 9:02
  • $\begingroup$ @Untitpoi Example: Theme 1050 and 3591. Right? $\endgroup$ – LeppyR64 Feb 28 '18 at 11:59
  • $\begingroup$ There are a few with just one person. They just need to be scheduled with at least that one person. It doesn't make much sense in real life, but the puzzle still works. $\endgroup$ – Dr Xorile Feb 28 '18 at 20:06
  • 1
    $\begingroup$ This almost sounds like something you could throw on code-golf as well. It'd be interesting to see what those folks come up with. $\endgroup$ – tfitzger Mar 9 '18 at 15:25
1
$\begingroup$

There are many sets of themes that require the exact same sets of participants. For example, the last 16 themes listed all have the same set of participants. Obviously, it would be more efficient to combine each set into a single meeting.

What I would recommend would be to enumerate all the distinct sets of participants required, and count how many themes correspond to each set. Then work with the sets with the smallest numbers of related themes. For those sets, find the ones with the highest overlaps between them. It should be obvious where meetings could be combined that would have a few employees wasting time because they are not interested int theme, but a larger number would benefit from having fewer meetings to attend.

$\endgroup$

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.