Dangling with Time Ranges
Usually, in our day-to-day programming, we work with time ranges or date ranges a lot. Iterating them, and finding specific facts related to them can be quite cumbersome and to be frank, most of the time people tend to write suboptimal algorithms for these types of tasks.
After dangling with time ranges for a while, I realized that 99% of the tasks related to time or date ranges can be completed with the complexity of O(nlogn). And most importantly, most of these problems can be solved using a simple single pattern.
When we talk about Time/Date ranges we are talking about a collection of the following types of objects. In this object, startTime is always equal or less than endTime.
{startTime: yyyy-mm-dd hh-mm-ss, endTime: yyyy-mm-dd hh-mm-ss }
Let’s learn the pattern and then see about the use cases. As I have repeatedly said the pattern is so simple and it has only three steps!
Step 1: Create a list of Time/Date elements from the Time/Date ranges collection
Step 2: Sort the Time/Date elements
Step 3: Iterate the Time/Date ranges while working with your conditions using flags
In step 1 we create a new collection from the Time/Date ranges collection as follows.
With the above transformation, a new collection would be created as follows.
[{time: yyyy-mm-dd hh-mm-ss, direction:”End”}]
Well, there is nothing to explain in step 2 right? Use whatever sorting algorithms you know and perform an ascending sort. Use startTime as the primary key for sorting and use endTime for tie breaking. If you ask me I would prefer Tim Sort as it gives the fastest results in most cases [O(n) or O(nlogn)].
With this sorted collection, we can do limitless things by just iterating them. And that’s step 3.
1. Combine Overlapping Time/Date ranges
With the sorted Time Elements list we can keep a flag for the number of overlaps while we are iterating the list. So we get the startTime of the first element and we keep counting the overlaps. The overlaps variable can be increased but eventually it would decreased. When the overlaps variable becomes 0 we get the endTime as the end of the combined period. After that continue the iterating and repeat the same. As I mentioned previously, the pattern is iterating a sorted list while keeping flags.
2. Identify Time/Date Periods with N overlappings
This time it’s bit more complex. But the pattern remains same. In here we mark the collapseStartTime at the moment that we see N overlaps. Then we mark the endTime of the collapsedTimeInterval at the moment we see the number of overlaps are changed. Keep in mind that it can be either N+1 or N-1. Regardless of whatever it is we marked that time as the end of the collapsedTimeInterval. Then we keep repeating the same process untill we reach the end of the list. (+1 / -1 must be from the smallest time entity (seconds, mili-seconds, days etc) of the timeElement that is considered.)
3. Get the non Overlapping Time/Date Periods
This one is a special case of the pervious one. The only thing that we have to do is make N=0 and vola! we get the non overlapping date ranges. I leave it to you to think about how that happens.
This is nothing but the power of sorted item iterations. The key thing to remember is almost all the Time/Date ranges problems can be solved much more effectively by adhering to this simple pattern.
What do you think? Have you ever found a problem that would break this pattern? I dare you to comment it!
(ps. I purposefully used images so that a lazy person can’t copy and paste :D. Always use code with understanding)
