Printable View
I am currently working on a ticketing kind of application
and one of the desired features, is searching a bay of seats for the largest group.
so im wondering are there any kind of algorithms or whatever that searches over a 2d graph and can spit out the largest group of available seats?
any tips welcome :)
thanks
how big is this place? cant the user just look at the grid and see what area is the biggest?
nope, itd also be good 2 list all available groups of 6 for example.
say 40, 000 seats, each bay has a map. so instead of hte user having 2 look at every bay, they can just use this.
(to be honest i think its kinda silly, but this is what they want!)
Obviously, you want to find all possibilities, you you're going to have to at least check every one even in the fastest case.
Ad you can do this.
Assuming you only want 6 in the same row, not 6 in a column, do this:
Algorithm:
(p.s. please excuse the C++ code)Code:int NUM_FREE = 0;
for(row = 0; row < NUM_ROWS; row++)
{
NUM_FREE = 0;
for(col = 0; col < NUM_COLS; col++)
{
if(seat.isempty())
NUM_FREE++
else
NUM_FREE = 0;
if(NUM_FREE >= TARGET_SIZE)
Is_free[row][col] = true;
}
}
After this, if the seat row x column c is the right-most in a group of TARGET_SIZE empty seats, then Is_Free[x][y] = true;
ohhh no, i mean BLOCK like find a block of 4 in this map
X 0 0 X 0
0 0 0 X 0
X X 0 X X
for example there is a block of 4. two in top row seat 2, 3, then in second row seat 2, 3.
tis a biatch i know
Well, can the block be any shape, or do they have to be rectangles?.
Otherwise you could flood-fill the free seats, and any set which has more than TARGET_SEATS seats is a block
make an array holdin the column height of empty seats with the length of a row, an array holding the position of latest occurrance of each column height in the current row, and three temporary variables holding the area, width and height of the so far largest block
now for each row, for each column,
- set at the row position in the first array, 0 if the seat is booked, otherways add one - this is the height of the empty column here.
- if the height was larger than the previous one, set at each index from the previous height+1 to the current height, in the second array, the row position - this will allow fast tracing back the largest block of specified height, for all blocks that fits in the new open area.
- if the height was smaller than the previous one, or if you've hit end of the row, calculate the block sizes for all blocks with height from the previous one's to and without the current height, by multiplying the height with the difference between the current row position and the one found in the second array(by specified height). If you've got a new record, update the temp vars.
keep iterating, each time you get more room their position is put down and each time you get less room, the block sizes are calculated. Hope you get the idea.
here's an illustration, just in case:
Code:122210
xxooxx
xoooox
ooO
height increasing to 3, set heights[3]=2 (position). If raised more, remember to put them all to 2.
123310
xxooxx
xoooox
ooooO
height dropping to 2, calculate 3*(4-heights[3])=6. if drops more remember to calculate for all dropped heights
I have one possible idea.
Are you suffieciently familier with masks and binary/boolean logic?
One method might be to use a "mask" shaped to the block size and shap of the disired area and the compaire the two
000
000
000
010
where 0 is the seat layout required.
1001001010
1100011100
1000000011
1000000011
1001001111
1110011010
1111111111
0101010101
is a map of seats where 1=taken 0=spare
now as I understand it you are looking for this result
000
000
000
000
indicating that full seets are full and emty seats required are empty. You would have to be carefull of making the "full area" too big but in priciple you could then search for any pattern untill you found a match.
the search pattern would be:
top left coner, test, LOOP: move one step to right, test END LOOP;
On All=0 do this
....
etc.
It's kinda like pattern matching basicly.