1

I am having the following probrem. I have two lists (separate Custom Objects). The first list contains a collection of time slots which are created either manually or based on a pre defined pattern. A slot record contains start time (Datetime), end time (Datetime) and a few other fields. The second list contains a collection of bookings. Each booking record contains again start time (Datetime), end time (Date time) and a few other fields. Start time, end time and length of both slots and bookings varies. The list A contains approx 10 000 records and the list B around 7 000 records.

What I would need to get is a combination of these lists so that I would have slots from list A populated in between bookings (list B) where it is possible without overlapping with any booking. I tried looping the lists but ended up with CPU time limit error (System.LimitException: Apex CPU time limit exceeded). Any suggestions?

enter image description here

Many thanks in advance!

Ollie

5
  • what r u trying currently, can we see that code? – Ganesh Bhosle Dec 19 '13 at 6:38
  • The code is already gone unfortunately but what i tried is two loops. Outer is the list A and inner list B. In the inner loop I had if-conditions to see if the slot can fit in between booking i and booking i+1. I think this results 10 000 x 7 000 = 70M iterations... – Ollie Dec 19 '13 at 6:44
  • I think one of the better way to handle such logic is to make sure your interface allows paging and thus you end up computing logic for lower number of records for he time slot you wish. – VarunC Dec 19 '13 at 6:48
  • I see. The problem with my case is that the data is presented in a calendar view. – Ollie Dec 19 '13 at 7:08
  • I apologize in advance for my answer. – sfdcfox Dec 19 '13 at 7:58
3

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.

1
  • Thank you sfdcfox for your comprehensive reply. It was very useful. I decided to go with Lock Step algorithm which worked well. – Ollie Dec 30 '13 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.