给定尺寸的所有矩形的搜索矩阵(选择座位块)

Question

所有,

我一直试图找出如何在一个座位内选择15张票.

编辑:问题是 - 如何找到给定尺寸的所有矩形(例如3x5)的免费座位？

下面是我的表,查询选择4个连续席位(或15或其他),这是好的...

但我想做的是选择说15个座位,这些可以分成多行,即3 x 5,但我希望它们被封锁在一起,即

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

也就是说,他们将在彼此前面排成3排.row9座位10到25,row8座位10到25,row7座位10到25.

还可能需要考虑座椅块是否具有不同数量的座椅,即角块可以呈弧形以在后部具有比前部更多的座椅.

以ehnaceing SQL或某些算法或某些PHP代码的形式提供的任何指导.一周的大部分时间里,我一直在捣乱自己的大脑.

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;

我的查询到了 - 它返回X席的块组合.

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

在此先感谢,需要更多信息,请问!

Answer 1

在mysql之外,用另一种语言解决这个问题要好得多.换句话说,你有一个座位矩阵,其中一些是被占用的(灰色的):

你想找到给定尺寸的所有矩形,比如3x5.您可以通过两次通过线性O(n)时间算法(n为座位数)非常有效地完成此操作:

1)在第一次通过时,按列从下到上,每个座位,表示可用的连续座位数:

重复,直到:

2)在第二遍中,按行,并查找至少5个大于或等于3的连续数字:

所以,最后,你得到:

产生解决方案:这些数字序列(绿色区域)是2个可能的自由座位3x5矩形的顶部边缘.

该算法可以很容易地增强到例如获得具有最大面积的所有矩形.或者,它可以用于找到N个座位的任何连续区域(不仅是矩形) - 只是在第二次通过期间,查找连续的数字序列,其总和至少为N.