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 count 0. weekday If the date is a count 0. holiday If the date is a and not a 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. weekday holiday : 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 . Therefore the complexity is , where is the distance between the dates and is the length of the array that contains the . We could use a Hash to store the and this would take down the complexity to linear. Complexity holiday NxM N M holidays holidays 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 the set of between two dates. And let’s call the set of between two dates. The number of between these two dates will be W weekdays H holidays workdays W-(W∩H). We now the ahead of time, therefore we can calculate the following before hand: schedule 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 as . And therefore we can calculate it in constant time. workdays (number of weeks x hours per week) + (hours between weekday of first day and weekday of last day) Calculate amount of time during on between two dates: holidays weekdays We will also now the ahead of time and we will do some calculations ahead of time too. We will iterate through every date between and and we will calculate the following: holidays first holiday last holiday Whether that date is a . holiday Number of that occurred on before that date. This are not actual business hours, but they would’ve been if they hadn’t been on a holiday. “business hours” holidays 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 fell during between and , we will just need to calculate: “business hours” holidays date1 date2 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 and . For right edge calculate hours and . left edge start time end of business day between start of business day 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 gem. I’ll compare the performance of my implementation against the 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 and the results from the tests are the following: Operating Hours Business Time here 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
