takeaway

I believe everyone should have snatching train tickets experience, every year at the end of the year, this is a feast. However, have you ever wondered how the train ticket snatching algorithm is implemented? Should not, let’s discuss one by one today. It’s not as hard as you think

Bitmap and bit operations

The basic use of Redis bitmap we have been introduced before, if not very familiar with the friends can see here redis bitmap basic operation and application

What we’re going to do here today is review bit operations

Grab tickets algorithm in detail

We in Beijing to xi ‘an this high-speed rail, for example, my route is from Beijing to xi ‘an, for example, if the car is only one ticket, so if you have other people, between the route from Beijing to xi ‘an to buy any one station, then I is can’t buy the ticket, in other words, for a single seat, all standing between must be the starting point to destination, no one to buy, That’s what counts as ticketed status.

Therefore, we can try to use Bitmap combined with upper level operation to achieve this scenario. Taking the above-mentioned Beijing to Xi ‘an as an example, we can simplify the problem

• For example, there are only four seats on a train

• Beijing to Xi ‘an, a total of 4 stops, in fact, is three sections, respectively, Beijing -> Shijiazhuang, Shijiazhuang -> Zhengzhou, Zhengzhou -> Xi ‘an

First, we construct an empty graph for each interval (0 for tickets, 1 for no tickets).

Next, let’s say someone buys a ticket from Beijing to Xi ‘an

For the action of buying tickets, for example, the seat no. 1 is assigned, so we directly set the seat no. 1 at all stations from Beijing to Xi ‘an as 1, as shown in the picture below

Then someone bought a ticket from Shijiazhuang to Xi ‘an

For example, seat 2 is allocated this time, so we just set all the tickets from Shijiazhuang to Xi ‘an to 1, as shown in the picture below

How do you know how many tickets are left?

In fact, to solve this problem is very simple, we directly put the above bitmap to do a or operation can be

Or the result of the operation has several zeros, indicating how many tickets are left.

conclusion

Actually solve the problem lies mainly in the construction of a bitmap, because the train ticket for one seat, as long as the starting point to the finish line in the middle occupied a certain interval (1), the characteristics of the whole seat is invalid, it is easy to think of the result of the use or operation to determine to buy tickets as a result, we took only four here is convenience to illustrate this, The actual bitmap should be as long as there are seats on the train. Ok, about snatching tickets algorithm we are introduced here, have you got it? Or do you have a better way to do it?