Booking problem

Question

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?

Answer 1

'Better' is a word that has only meaning in relation to a cost-function (some function to map quality to a comparable entity like a number).

If we know nothing about the distribution of 'occupied' and 'available' hours, the one bit per hour idea guarantees a fixed amount of needed memory, no matter how the distribution of 'occupied' and 'available' is.

I could imagine, that in most hotels, the guest stay in most cases for much longer than 1 hour. If your data is of this kind, where occupied periods most over spread over a lot of hours, it might be also efficient to store the 'occupied'-intervals instead of a bit per hour.

You are right on all common systems, bit-operations are really fast, also (depending on the size of a long) you compare 64 bits at once.

But checks get tricky, if you search for intervals crossing long-boundaries. So be sure you considered all cases.

To make this simpler, let a long be 8 bits:

possible intervals to check:

... 00000000 xxxxxxxx xxxxxxx xxxxxxx 000000 .. interval starts and ends at a long-boundary

... 000xxxxx xxxxxxxx .... interval starts in the middle of a long

... xxxxxxxx xxxx0000 .... interval ends in the middle of a long

... 00xxxxx0 ... interval stards and ends within the same long

In the last 3 cases you must ensure correct masking of the relevant bits for your check