15

全部，

我一直在努力研究如何在一个座位区中选择 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 行，都在彼此的前面。第 9 排座位 10 到 25，第 8 排座位 10 到 25，第 7 排座位 10 到 25。

还可能需要考虑一个座位块是否有不同数量的座位，即角块可能是弧形的，以使后面的座位比前面的座位多。

以增强 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

在此先感谢，需要更多信息，请询问！

4

7 回答 7

14

这个问题在mysql之外用另一种语言解决得更好。换句话说，您有一个座位矩阵，其中一些已被占用（灰色的）：

在此处输入图像描述

并且您想找到给定尺寸的所有矩形，例如 3x5。您可以通过两次通过线性O(n)时间算法（n 是座位数）非常有效地做到这一点：

1）在第一遍中，按列从下到上，对于每个座位，表示最多可用的连续座位数：

在此处输入图像描述

重复，直到：

在此处输入图像描述

2) 在第二遍中，逐行查找至少 5 个大于或等于 3 的连续数字：

在此处输入图像描述

所以，最后，你得到：

在此处输入图像描述

这产生了解决方案：这些数字序列（绿色区域）是 2 个可能的 3x5 空闲座位矩形的顶部边缘。

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

于 2011-09-08T19:07:51.683 回答
3

根据您的描述，这不是数据库问题，而是算法问题。我建议平铺模式可能是四叉树或空间填充曲线。也许 MySQL 中的空间索引也可以帮助您解决问题。一个 si 将 2d 平面细分为 4 个图块。

于 2011-08-07T07:10:23.283 回答
1

我来这里是为了寻找 Python 解决方案。这是我的，它返回所有位置：

import numpy

s = '''0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0'''

area = 15
nrows = 6
ncols = 11
skip = 1

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if a[r][c] == skip:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            if (dh+1)*minw == area:
                print(
                    'area', area, 'row', r, 'col', c,
                    'height', dh+1, 'width', minw)

输出：

area 15 row 4 col 8 height 3 width 5
area 15 row 5 col 10 height 3 width 5
于 2015-05-24T00:12:54.030 回答
0 
    $nr_tickets = 15; // or whatever


// build an array of different configurations:
// since you always want people as close to eachother as possible this is a suggestion:

$configurations = array();
for($columns=1; $columns<=$nr_tickets; $columns++)
{
    $BLOCK = array();
    $remainder = $nr_tickets % $columns;
    // $nr_tickets - $remainder = greatest number divisible exactly by $i (columns) which is the number of rows you want.
    $rows = (($nr_ticket-$odd) / $i);
    //$configurations[$columns] = $rows // make a rectangle configuration or $columns x $rows with $remainder tickets left.
    $BLOCK[] = array_fill(0, $columns, array_fill(0, $rows, X); // multidimensional array
    for($a=0; $a<$odd; $a++)
    {

        // each of the remainder seats need to be 'stuck on to the block/rectangle of seats you already have, this can be done in
        // ($rows + $columns * 2) - $a ways for each of the consecutive non-assigned tickets
        /*
            lets say you have a block of 2x7 (s) with 1 (N) possible ticket left 
                   N  N  N  N  N  N  N  
            N  s  s  s  s  s  s  s  N 
            N  s  s  s  s  s  s  s  N   
               N  N  N  N  N  N  N 
        */
        // so basically we can add a ticket to each of the rows and for each of those configurations we need to add $a more
        // this may be simpler with a recursive function call that adds $a more for each 1 ticket you add here to a row or a column. 
    }


}



// now you can go select all different permutations of settings from the database and select one you like :)
于 2011-08-09T22:05:31.013 回答
0

如果您可以以编程方式创建查询，我将为每一行编写一个查询并将其组合使用UNION，然后只需使用相同的查询 X 次，只需将它们附加到UNION.

来自mysql手册

UNION 用于将多个 SELECT 语句的结果组合成一个结果集。

于 2011-08-11T06:12:05.297 回答
0

首先，我将假设大多数场所都可以映射（即使是近似的）到方形网格，即。座位没有奇怪的设置或奇怪的偏移。因此，每个座位周围最多可以有八个座位。

CREATE TABLE Seat {
   SeatID int,
   Status int,
   ...
   NorthID int,
   NorthWestID int,
   WestID int,
   ...
   NorthEastID int
}

从本质上讲，我将能够创建一个“座位图”并根据查询的需要走动它。然后，您可以创建查询以获取某些形状或块。

3x3 网格将包括选择一个开放座位，其中所有方向的直接链接座位也开放。是的，这将是 8 个 JOINS，但请稍后尝试并优化。

SELECT * FROM Seat x
INNER JOIN Seat n ON x.NorthID = n.SeatID
INNER JOIN Seat nw ON x.NorthWestID = n.SeatID
...

一个 1x15 块将是一个查询，用于选择一个开放座位，您可以在其中沿着 EastID 或 WestID 加入 14 个深度。

您可能可以通过编程方式概括和生成查询。

PS：根据您使用的引擎，您可能具有内置的空间功能。

祝你好运。

于 2011-08-14T03:54:14.317 回答
0

这是一个简单的方法。它可能不足以满足您的需求，但它是一个开始的地方。

让我们简化问题并考虑一个名为seat具有列row、col和的表taken。前两个是整数，另一个是布尔值。我们想要找到row并col限制在某些大小的矩形的值，其中taken普遍是错误的。我们将尝试一个查询，它移动一个矩形并记录其中的taken值的总和。我们想要的矩形总和为零。

假设我们正在寻找 2x2 的开放式座位块。这是查询。

SELECT row, col,
       (select sum(taken) from seat as s2
               where s2.row >= s1.row and s2.row < s1.row + 2
                 and s2.col >= s1.col and s2.col < s1.col + 2) as count
       FROM seat as s1

只需过滤此查询的输出 where count = 0。row和将col指定打开块的左上角。最后一个怪癖是，您需要过滤掉切得太靠近座位右侧或底部边缘的左上角，因为这会人为地减少它们的总和（测试的矩形被剪裁到座位的边缘）。在 2x2 块的情况下，这意味着row < max(row)和col < max(col)。

现在在寻找 15 个相邻座位的情况下，您正在寻找 15x1、1x15、3x5 和 5x3 的矩形。您可以将上述查询转换为采用矩形宽度和高度参数的存储过程，然后使用这些大小调用它，直到找到匹配项。

于 2011-08-14T04:39:44.083 回答