The initial task was to find very quickly, free time for resources, let say - hotel rooms, services availability. I came with following model:
Let say we have 24h in 1 day, and 365(366) days in a year. 1) We have a sequence of bits
timetable=0001011....000, length(timetable) = 24*365 = 8760 0 is busy 1 is free.
So if we need to merge two timetables output is: 1 && 1 = 1 free and free give free, 1 && 0 or 0 && 0 = 0, busy and free or busy and busy give busy.
2) We have array of sequences:
arr = [timetable1, timetable2, timetable3....N]; N < 1,000,000
representing free/busy intervals for a timetable of some resources (hotel room, or any service counting in hours).
The task is the following:
We need to find free time in the following interval (i,j). i<>j, 0
-i,j can represent days interval in year, so we can reduce the initial long array by the rule above. Example, (120, 125) -i,j can represent hours interval in year, so we can use same array as above.
The total should be around 50-100 ms.
My algorithm is the following: 1) input is a sequence of bit 11111...1111 2) make bitwise "and" (&) with each timetable.
Bitwise operations are really fast, so I think this should be an optimal solution. Does anyone think that can be done better?