Is there a standard algorithm for balancing overlapping objects in buckets?

Question

I have a group of users with a given start and end time, for example:

{ Name = "Peter", StartTime = "10:30", EndTime = "11:00" }, { Name = "Dana", StartTime = "11:00", EndTime = "12:30" }, { Name = "Raymond", StartTime = "10:30", EndTime = "14:00" }, { Name = "Egon", StartTime = "12:00", EndTime = "13:00" }, { Name = "Winston", StartTime = "10:00", EndTime = "12:00" } 

I want to put them in buckets, depending on the fact that they overlap (based on a custom threshold, for example, they should overlap for at least half an hour). I want the buckets to be ideally 4 pieces large, but any range from 2-5 is valid.

There are no 4 people in the above example, so I will have a bucket of 3 (Peter, Raymond, Winston) and one of 2 (Dana, Egon).

I prototyped an algorithm that seems to rely on chance rather than science:

• Order list by StartTime
• Create an empty container
• Select the first user from the list
• Make sure the user is against all users in the bucket
• If this user overlaps with everyone in the bucket, put that person in him and remove him from the list
• If the bucket has an ideal size (4), or if I loop and check the same user more than three times, close the bucket and create a new empty one.

This works well for the first few buckets, but leads to buckets that have only 2 people that can be combined better.

I could change the algorithm to remove all the ideal buckets from the list and shuffle and try something else, but I think this should be a common problem - is it like assigning a shift for workers or maybe a knapsack problem .

Does anyone know a standard algorithm for this type of problem?

(Tagged combinatorics, because I think this is the area of ​​mathematics that she applies, correct me if not)

Answer 1

tl; dr: dynamic programming to win (time O (sort (n)).

First, note that bucketing contiguously in the start order is excellent.

Suggestion (defragmentation): Let a, b, c, d be different users, such as StartTime(a) ≤ StartTime(b) ≤ StartTime(c) ≤ StartTime(d) . If X and Y are valid codes, such as a, c ∈ X and b, d ∈ Y , then X - {c} ∪ {b} and Y - {a} ∪ {d} are also valid buckets.

I only know how to prove this with the tedious case analysis (omitted).

Result: you can pretend that you are breaking a paragraph into lines, where the “paragraph” is a list of users in the start order, and each “line” is a bucket. There is an algorithm due to Knuth and Plass for optimal line breaks, where the penalty for a given line is a more or less arbitrary function. You can make buckets with 4 cost 0, buckets 3 cost 1, buckets 2 cost 2 and, for example, buckets 1 cost 100.

Answer 2

Based on your problem, I would probably do something like the first creation of a class called "Man", something like this. Give this class the attributes Name, Start Time, and End Time.

 class Person { public string name; public double start_time; public double end_time; } 

Then put them in some sorted list of type Person. (I also save time as doubling. You can convert them back to times simply by multiplying any decimal part of the time that I have by 60/100.

Afterwords you will create a list of buckets into which you can add new buckets if necessary. Then you sort the list based on the threshold that you define, and if the two objects that are compared overlap based on that threshold, then they both enter this Bucket. If they do not overlap, go to the next forging, if there is overlap, then add it to this Bucket, etc., Until you get to the last Bucket. If you went through all the Buckets and still do not overlap, create a new Bucket for this object.

 class MainFunc { static void Main(string[] args) { //makes a function to check if 2 values overlap over a threshold //st stands for start time and et stands for end time public bool IsWithinThreshold(double st1, double st2, double et1, double et2) { double threshold = .5; if(st1 >= et2 || st2 >= et1) { return false } else { if(st1+threshold <= et2 && st1+threshold <= et1 || st2+threshold <= et1 && st2+threshold <=et2) { return true; } else { return false; } } } // makes objects of type Person with attributes of name, start time, and end time Person Peter = new Person(); Peter.name = "Peter" Peter.start_time = 10.5 Peter.end_time = 11.0 Person Dana = new Person(); Dana.name = "Dana" Peter.start_time = 11.0 Peter.end_time = 12.5 Person Raymond = new Person(); Raymond.name = "Raymond" Raymond.start_time = 10.5 Raymond.end_time = 14.0 Person Egon = new Person(); Egon.name = "Egon" Egon.start_time = 12.0 Egon.end_time = 13.0 Person Winston = new Person(); Winston.name = "Winston" Winston.start_time = 10.0 Winston.end_time = 12.0 //puts objects of type Person into an unordered list List<Person> people = new List<Person>(); people.Add(Peter); people.Add(Dana); people.Add(Raymond); people.Add(Egon); people.Add(Winston); //sets up a list of lists of People (Buckets in our case) List<List<Person>> Buckets = new List<List<Person>>; //sets up an intial Bucket and adds the first person on the list to it List<Person> Bucketinitial = new List<Person>; Bucketinitial.add(people[0]); for(var i = 1; i < people.Count; i++) { for(var j = 0; j< Buckets.count; j++) { //sets a checker to make sure that all objects in a given Bucket overlap with the person we are checking bool overlap = true; for(var k = 0; k< Buckets[k].count; k++) { overlap = overlap & IsWithinThreshold(people[i].start_time,Buckets[j][k].start_time,people[i].end_time,Buckets[j][k].end_time) } if (overlap == true) { Buckets[j].add(people[i]) } //if all the objects in a bucket don't overlap with the person... //... make a new Bucket with that person else { List<Person> NewBucket = new List<Person>; NewBucket.add(people[i]); Buckets.add(NewBucket); } } } } } 

Then simply add a print command to print the attributes of the name of each object in each bucket of the bucket list. Please leave a comment if you have questions / problems, greetings.

Answer 3

You can change your algorithm to include an interval tree to speed up your search.

• Order list by StartTime
• Adding Elements to the Spanning Tree
• Create an empty container
• Select the first item from the list.
• Find the earliest items during the threshold time of the first item that fill the bucket using the interval tree interval search
• Remove items from the list.
• If the list is empty, stop otherwise go to step 4

Basically, you move from left to right in interval steps (set by your custom threshold), using the interval tree to quickly query the closest elements when moving.