CODEWITHSUNDEEP
algorithmintervalstimeslots
Daniel Becker
Daniel Becker

Reputation: 821

Find all intersections for m timespans of n parties

I just can't figure out a nice way to solve the following problem:

For an event I have n parties (party_id) taking part. Each party has m availabilities for said event in the form of start_date and end_date.

What I would like to know is all possible combinations of overlapping availabilities containing exactly one availability for each party_id. I discovered Interval Trees (https://en.wikipedia.org/wiki/Interval_tree) which might be utilized, but as I said I can't quite figure it out.

So thanks for any thoughts on that!

Upvotes: 1

Views: 54

Answers (1)

comingstorm
comingstorm

Reputation: 26117

The straightforward way is sort all your events (start_date and end_date alike) by time. Then go through this list in chronological order, while keeping track of all "active" parties (i.e., those which have started, but not stopped).

The above method is a batch process, which should let you find all possible combinations of a given schedule easily. The interval tree you mention is useful in cases where you want to incrementally update your set of parties -- the datastructure can make individual queries about a particular time much cheaper than re-running the batch process for each update or query.

Upvotes: 1

Related Questions