Answer to: Recommended data structures/algorithms for checking peoples' availability schedules

Interesting problem. My university used simulated annealing to shift lectures, rooms, times, and students around to form a schedule which they manually tweaked before publishing for the semester. Sounds to me like you want this to be somewhat more dynamic though. A spatial tree feels right for this. An R*-tree would be ideal but others can do the job. That's a region Tree with Leaf-node walking. We need two of them for a given period of time (a day, a week, a month, up to you really). The first stores the events, the second attendee's availability. Both tree will start with a single node containing no entries, marked for the entire time that the tree represents. This is so that latter we don't have to check if nodes have consecutive time stamps, we know that the structure is dense, therefore the next node is always for the slot of time after this one. When a user says I'm available between time x and time y, you insert them into the tree for that region of time. We follow the tree down break apart the node found if it doesn't start at the same time the attendee starts being available. Add them into the node, and each subsequent leaf node until you find the node that matches the attendees end of availability. (Break it apart if that node extends past it). Repeat for each interval of each users time. Given your system is probably online this allows users to add new availability easily at their leisure. Bulk inserts are also possible. Removing time is similar, just avoid the merge step. Because time is always marching forward you'll pay more to remove unnecessary nodes. Perhaps rebuild the tree offline if there has been some threshold of deletes reached, or if a tree built for say two years from now becomes next months tree. Do all of the above for the events as well. To find out the list of available attendees for an event. lookup up the attendees tree for the start of the time period, and grab a list of each leaf from there to leaf containing the end time. Intersect the lists on those nodes Whoever is left is available. To find the events available, grab the events tree Per interval of available time -> Find the first leaf node that starts after the attendees becomes available, and union with each next node until it ends after the attendee becomes unavailable. Grab the nodes on either side of the union and subtract them from the union. This is the list of available events for that attendee. Why? For the events finding attendees: the fact that attendees are listed as available in a region of time is all that is needed. Intersecting with each leaf node that makes up that time ensures they are available for the entire block of time. If that's a single node great. For attendees finding events: the event needs to be present at least once in the period of time they are available. But the event might start earlier or end later, that is why we subtract the node starting before and the node ending after the attendee's availability - even if those nodes are also partially in the region of availability with the attendee. Their presence there means they must start before or end after. An optimisation might be to make the tree for each set of PreReqs that an Antendee has, or an Event needs. This allows you to reduce the sets to be explored upfront. The downside is that the event/attendee will need to be added to multiple trees for the same time period as attendees should always show up in the no prereqs tree. Another optimisation is to make the lists of events users a bit table, and have a secondary entry table to properly reference them. This allows for quick bit ops for intersection, union, and subtraction. It also make node splitting a faster op (copy binary blob, versus duplicating references). It does add in a translation step of mask to actual data, but that isn't much of a slow down. This works great for one off events, but you probably want to offer some better services like highlighting if there is enough event capacity for those who wish to attend, and how flexible your attendees are. So Attendees wishlist a event type. An organiser wants to know if a given set of times satisfies demand. When an attendee wishes for the event type we add their availabilities to a new tree just for the event type. The organiser can now see this tree plotted out as a graph over a day/week/month and can position events over periods of time where availability is enough to warrant it. Even better with a set of classes in mind we can ask for lists of attendees. We just count how many times an attendee is available for an entire class and gives us a flexibility measure for each attendee. The organiser knows who to prioritise, or how good their offering of times is. You should be able to do something similar for the availability of events given conflicting wishes. To guide an attendee into choosing events that give them more flexibility later.