CODEWITHSUNDEEP
pythonalgorithmgroupingmatching
aryann
aryann

Reputation: 13

Algorithm to group people together based on their available timeslots/ calendar

I have generated a sample dataset of 1000 people with their available timeslots during the day. Each timeslot is a 30 minute interval during the day. 0 indicates they are free during that timeslot and 1 indicates they are busy.

for example:

| Time        | Sally | Mark | Nish |
| ------------| ----- | ---- | ---- |
| 0900 - 0930 |   0   |  1   |   1  |
| 0930 - 1000 |   1   |  0   |   1  |
| 1000 - 1030 |   1   |  1   |   1  |
| 1030 - 1100 |   1   |  0   |   1  |
| 1100 - 1130 |   0   |  1   |   1  |
| 1200 - 1230 |   1   |  0   |   0  |

I want to create the maximum number of groups of 5 people that have at least one available timeslot in common. Each group should be mutually exclusive. I want to maximize the number of successful groups that are created.

At present, I am using a pretty crude algorithm. I sample the dataset for 5 people then check if they have an available timeslot in common. If they do, then I remove them from the dataset and repeat the process. If they do not have a common timeslot available, I resample another 5 people and keep trying until I find a sample of 5 with a common timeslot. If after a 1000 resamples, it is unable to find a sample of 5 that meets the criteria it stops.

This seems very inefficient to me and I was wondering if there is a better way to do this.

Upvotes: 1

Views: 1038

Answers (2)

Axel Kemper
Axel Kemper

Reputation: 11332

I would tackle the task according to the following pseudo code:

For every timeslot count the number of available people.
Sort the timeslot in ascending order of available people.

For every person, count the number of available timeslots.
Sort the people in ascending order of available timeslots.

While people are available:
    Enumerate the sorted list of timeslots:
        Repeat for the timeslot as long as 5+ people are available
            Collect five people available for this timeslot
            Remove them as one group from the list of people.
            Decrease the avaiblability count of the timeslot. 
    Break the while loop if no group was formed during the iteration

The rationale behind the sorting is to use rare timeslots first. Assign people with few choices first. This leaves the crowded timeslots and the people with many choices for the final rounds and thus enlarges the chance for more groups.

Upvotes: 3

Prune
Prune

Reputation: 77910

Yes, your Monte Carlo solution is very time-consuming. Depending on the density of available slots, it may be fatally flawed.

Instead, construct viable sets. For each slot, build a set of all people available. Now, all you need to do is iterate through all of the 5-member subsets of that set. Repeat this for each time slot. You now have all sets of five members with at least one time slot in common.

Upvotes: 0

Related Questions