Search matrix for all rectangles of given dimensions (select blocks of seats)

Question

All,

I have been trying to work out how to select say 15 tickets within a single block of seats.

EDIT: the problem is - how to find all rectangles of given dimensions (say 3x5 for example) of free seats?

The below is my table, and the query selects 4 consecutive seats (or 15 or whatever) which is fine...

But what I want to do is select say 15 seats, these may be split over multiple rows, i.e. 3 x 5, but I would want them to be blocked together i.e.

row 9 ..(some seats)..[5 seats]..(some seats)..
row 8 ..(some seats)..[5 seats]..(some seats)..
row 7 ..(some seats)..[5 seats]..(some seats)..

I.e. they would be 3 rows all in front of each other. row9 seats 10 to 25, row8 seats 10 to 25, row7 seats 10 to 25.

Also may need to consider if a block of seats have varying number of seats i.e. a corner block may be in an arc to has more seats at the back than the front.

Any guidance in form of ehnaceing the SQL or some algorithm or some PHP code. I have been wracking my brain for most of the week now.

CREATE TABLE `seats` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `event_id` int(11) DEFAULT NULL,
  `performance` int(11) DEFAULT NULL,
  `block` int(11) DEFAULT NULL,
  `row` int(11) DEFAULT NULL,
  `seat` int(11) DEFAULT NULL,
  `status` int(10) DEFAULT 1,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

My query to-date - which returns combinations of blocks of X seats.

SELECT    a.event_id, a.performance, a.block,
          a.row, a.seat AS start_seat,
          a.seat + (4 - 1) AS end_seat,
          4 AS requested_seats,
          a.id AS start_allocation_id
FROM      seats a
          LEFT JOIN seats b ON
              a.event_id = b.event_id AND
              a.performance = b.performance AND
              a.block = b.block AND
              a.row = b.row AND
              a.seat < b.seat AND
              b.seat < a.seat + 4 AND
              b.status = 1
WHERE     a.status = 1 AND
          a.event_id = 1
GROUP BY  a.seat
HAVING COUNT(b.seat) + 1 = 4
ORDER BY performance

Thanks in advance, need more info please just ask!

Answer 1

This problem is much better solved outside mysql, in another language. In other words, you have a matrix of seats, some of which are occupied (grey ones):

and you want to find all rectangles of given dimensions, say 3x5. You can do this very efficiently by two pass linear O(n) time algorithm (n being number of seats):

1) in a first pass, go by columns, from bottom to top, and for each seat, denote the number of consecutive seats available up to this one:

repeat, until:

2) in a second pass, go by rows, and look for at least 5 consecutive numbers greater or equal to 3:

so, finally, you get:

which yields the solution: these number sequences (green areas) are top edges of the 2 possible rectangles 3x5 of free seats.

The algorithm could be easily enhanced to e.g. get all rectangles with maximum area. Or, it could be used to find any continuous regions (not only rectangle-shaped) of N seats - just, during the second pass, look for continuous sequence of numbers which sums up to at least N.

Answer 2

From your description this isn't a database problem but an algorithmic problem. I suggest a tiling schema maybe a quadtree or a space-filling-curve. Perhaps a spatial-index in MySQL would help you solve your problem, too. A si subdivide the 2d plane into 4 tiles.