# Booking problem

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).

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?

• You want to merge up to a million timetables? I would think you'd need a way to filter that down (like an index) before you did the merge. Example: for each timetable could track "longest available slot" - that way if you need 6-week slot you can easily filter out any timetable that doesn't have any 6-day slots. Commented Mar 12, 2020 at 14:35
• You want to merge up to a million timetables? - Yes. To get free items. Commented Mar 12, 2020 at 14:39

'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

• 1) values will be stored in shorter format. But the conversion will be in format of bits. 2) interval check I want to simplify but not using long, just array and sub-array of bits. Commented Mar 12, 2020 at 15:01
• @Alexandr: Be careful depending on your programming language an array of bits might need much more memory than you expect (e.g. in java a `boolean` needs, depending on the VM up to 64 bit (see here: docs.oracle.com/javase/specs/jvms/se7/html/… )). Commented Mar 12, 2020 at 15:24
• @Alexandr also using a LONG[] can speedup the check up to 64 time, because you compare 64 bits with one instreuction. Commented Mar 12, 2020 at 15:30