How to calculate business time between two times efficiently

Problem

Given a company’s work schedule and two arbitrary times in two arbitrary days, we want to calculate the amount of time between these two times that falls inside the company’s work schedule (accounting for holidays too).

Example

Given a company based in the United States that opens Monday-Friday 9:00–17:00, how much time is there between Monday November 21st at 14:00 and Thursday December 1st at 11:00? Notice that Thursday November 24th is Thanksgiving and the company is not open:

So, in this case, we have:

• Nov 21st: 3 hours from 14:00 to 17:00.
• 6 full working days: 6 * 8 hours = 48 hours.
• Thursday Dec 1st: 2 hours from 9:00 to 11:00.

Total: 53 hours.

Brute force solution

Iterate through all the dates in the interval:

• If the date is not a weekday count 0.
• If the date is a holiday count 0.
• If the date is a weekday and not a holiday calculate business hours in day. For dates days outside of the edges of the interval it’s just closing time-opening time. For dates on the edges we would need to calculate the intersection.

Complexity: As you can see we need to loop through all dates inside of the interval and for each of the dates we need to check if it’s a holiday. Therefore the complexity is NxM, where N is the distance between the dates and M is the length of the array that contains the holidays. We could use a Hash to store the holidays and this would take down the complexity to linear.

Optimal solution

Step 1

Calculate business time inside the interval excluding the edges, this way we can count full working days and weeks.

Let’s call W the set of weekdays between two dates. And let’s call H the set of holidays between two dates. The number of workdays between these two dates will be W-(W∩H).

We now the schedule ahead of time, therefore we can calculate the following before hand:

• How much business time there is during a natural week. (eg 40 hours)
• How much time there is between any combination of two weekdays, for instance, between Monday and Tuesday there are 16 hours, Monday and Wednesday there are 24 hours, Sunday and Wednesday there are 24 hours, …

This way we can calculate the total time during workdays as (number of weeks x hours per week) + (hours between weekday of first day and weekday of last day). And therefore we can calculate it in constant time.

Calculate amount of time during holidays on weekdays between two dates:

We will also now the holidays ahead of time and we will do some calculations ahead of time too. We will iterate through every date between first holiday and last holiday and we will calculate the following:

• Whether that date is a holiday.
• Number of “business hours” that occurred on holidays before that date. This are not actual business hours, but they would’ve been if they hadn’t been on a holiday.

So the pseudo-code for this calculation would look like this:

holidays = [...] // we are passed an array with all the holidaysholiday_hours = 0holiday_info = {}

for date in range(holidays.first, holidays.last) doholiday = date.inside?(holidays)holiday_info[date] = {holiday: holiday,holiday_hours_before: holiday_hours}

if holiday and date.weekday? doholiday_hours = holiday_hours + business_hours_in(date)endend

This way if we want to calculate how many “business hours” fell during holidays between date1 and date2, we will just need to calculate:

holiday_info[date2 + 1] - holiday_info[date1]

Which can be calculated in constant time.

Step 2

Calculate business time on the edges of the interval:

• If the edge doesn’t fall on a weekday count 0.
• If the edge is a holiday count 0.
• Otherwise, for left edge calculate hours between left edge start time and end of business day. For right edge calculate hours between start of business day and right edge end time.

All this can be calculated in constant time too.

Operating Hours Gem

To show an implementation of this in Ruby, I created the Operating Hours gem. I’ll compare the performance of my implementation against the Business Time gem, which uses a brute force implementation. I’ll calculate a 1000 times the business time between two different date/times (from the same day all the way to a year apart). Assuming opening hours are 9 to 5 and we are passed the holidays between 10 years ago and 10 years in the future. You can check the tests I ran here and the results from the tests are the following:

Business time:Distance | Execution time | Result--------------- | --------------- | ---------------1 year apart | 24.077092 | 7257600.06 months apart | 12.693819 | 3744000.03 months apart | 6.426698 | 1814400.01 month apart | 2.466015 | 576000.02 weeks apart | 1.459892 | 259200.01 week apart | 1.00986 | 115200.02 days apart | 0.776951 | 28800.01 day apart | 0.839757 | 28800.0Same day | 0.595277 | 14400.0

Operating Hours:Distance | Execution time | Result--------------- | --------------- | ---------------1 year apart | 0.00949 | 72576006 months apart | 0.01707 | 37440003 months apart | 0.012577 | 18144001 month apart | 0.029238 | 5760002 weeks apart | 0.018997 | 2592001 week apart | 0.019849 | 1152002 days apart | 0.010557 | 288001 day apart | 0.016287 | 28800Same day | 0.020898 | 14400