[SalesForce] Populating time slots between reservations in a list

There are at least three ways to accomplish this: b-trees, maps, and optimized lists.

B-tree (binary tree)

A b-tree reduces the time complexity by allowing you to perform a binary search on the source data, reducing the initial complexity from 10,000 rows to search to 13 rows. It works because the tree structure stores data in a balanced way. Example:

                      12pm
                    /      \
                 6am        6pm
                /   \      /   \
             3am     9am  3pm   9pm

The problem, of course, is building a b-tree. I recommend a good article on Wikipedia or some programming website. In essence, though, you have nodes that look like this:

public class BNode {
    public DateTime nodeValue;
    public BNode lessThan, greaterThan;
}

To find a specific date/time coordinate, you examine the root node; if the value is an equal match, you have a result, otherwise if the search value is less than the node value, follow lessThan, otherwise follow greaterThan. In this way, you're performing a "binary search" which can run through 10,000 records in 14 iterations (a b-tree holds a power of two at each level, and 2^14 is 16384 values, more than enough to hold 10,000 records).

Benefits: Can store as granular time as possible. Detractors: B-trees are "advanced" and require planning to get efficient algorithms. Requires significant recursion to build initial list and final list, so initialization is slowest of the three solutions, and list building is equally slow.

Optimized Lists

Assuming you have a list of records sorted by time intervals, either ascending or descending, you can also perform a binary search without the B-tree, which is probably easier to conceptualize. Again, you start at record 5,000, compare the current value to that value. If it is less than, move to 2,500, if it is greater than, move to 7,500. You've probably done this without knowing it if you played "guess that number", where the "host" picks a number between 1 to 10. Most people would guess like this: 5 (more), 7 (less), 6 (correct), or 5 (less), 3 (less), 2 (less), 1 (correct). In other words, closing the gap by half each time, you can arrive at the correct answer in no more than 4 moves.

Benefits: Lists have a native sort function, so you spend less time writing code figuring that part out. Granular time frames are not problematic. No duplicates, final list loads fast. Detractors: Because you're trying to binary search on non-binary-sized data, you have to be careful not to round incorrectly, or you can miss spots in the time line. Also, the size of the array may change with each booking, since a single booking may consume multiple time slots.

Maps

This concept can work as well. First, you start with a map:

// TimeEntry is assumed to be a class
Map<DateTime, TimeEntry> entries = new Map<DateTime, TimeEntry>(); 

From here, you can first load all of the time entries into the map by time. This is a linear process, and the map can easily hold 10,000 values. This would have a relatively fast load time, and each result can be found in exactly one iteration; searches are in linear time.

Benefits: Simple code, linear searching. No sorting is required at all, and each element can be found instantly. Detractors: You would need to either store the time entries for each minute or second if you wanted that level of granularity, or remember to round to the correct granularity, because you can't depend on the order of the list, and you can't find approximate keys, only exact keys. Also, if you store the same entry multiple times (to represent spans of time), you may need a second map to correctly remove all the entries. This can make deduplicating the final list a nightmare as well.

Next Steps

Once you've picked a method to use, you can use the following pseudo-code:

Load the available time slots
Load the current bookings
For each booking
    Replace the time slot(s) covered with the appropriate booking.
End for

Alternatives?

You could avoid this entire mess by adding a single lookup field to the slot object; when a booking is created or modified, it would assign itself to that lookup field by trigger for each matching slot. This means you only need two queries, interleave the results, and output them. This assumes that slots will cover unique time periods and that no more than one booking can consume a time slot. More complex scenarios are also possible with some ingenuity (e.g. many-to-many connections to detect conflicting bookings).

Lock Step (Alternate algorithm)

Query both lists
Sort by ascending time
While both lists are not empty
    if the first booking in the list starts after the end of the slot
        add the slot to the output list
    end if
    remove the slot from the source list
    if the first slot in the list occurs after the end of the booking
        add the booking to the output list, remove from source list
    end if
End While

Hints

Don't use a loop-loop construct. Use maps, learn b-trees, or learn binary searching through arrays. There are probably millions of articles on how to do each on the Internet, but your approach should meet your skill level. Don't take on b-trees straight off unless you feel comfortable with them.

Edit

I just realized this entire answer kind of fails to emphasis the main point. Don't look for which slots can fit between which bookings. Instead, create a combined list of slots and bookings, and each time a booking covers a slot, remove the slot from the list, and put the booking in its place. This way, you're actually just building the results directly.