Searching a seating map for the largest group

[SkiNLaB]

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

[dis1411]

how big is this place? cant the user just look at the grid and see what area is the biggest?

[SkiNLaB]

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

[sql_lall]

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:

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;
    }
}

(p.s. please excuse the C++ code)

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;

[SkiNLaB]

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

[sql_lall]

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

[kedaman]

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.

[kedaman]

here's an illustration, just in case:

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

[Matt_T_hat]

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.