【SQL】サウナ、2人並んで座れる席を見つける

# 横1列のサウナにおいて、2人並んで座ることのできる席を見つける

![スクリーンショット 2023-01-07 12.28.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/536974/5c814f4f-9394-f0d6-4cc9-b6b2372826b1.png)

最初は、サウナ内の席は横一列のみになっていると仮定して進めます

`sauna`テーブルを作成します

```sql
CREATE TABLE sauna
(seat   INTEGER NOT NULL  PRIMARY KEY,
 status CHAR(2) NOT NULL
 CHECK (status IN ('○', '×')) );

INSERT INTO sauna VALUES (1,  '×');
INSERT INTO sauna VALUES (2,  '○');
INSERT INTO sauna VALUES (3,  '○');
INSERT INTO sauna VALUES (4,  '○');
INSERT INTO sauna VALUES (5,  '×');
INSERT INTO sauna VALUES (6,  '×');
INSERT INTO sauna VALUES (7,  '○');
INSERT INTO sauna VALUES (8,  '○');
INSERT INTO sauna VALUES (9,  '○');
INSERT INTO sauna VALUES (10, '×');
INSERT INTO sauna VALUES (11, '×');
INSERT INTO sauna VALUES (12, '×');
INSERT INTO sauna VALUES (13, '○');
INSERT INTO sauna VALUES (14, '×');
INSERT INTO sauna VALUES (15, '×');
```

```
postgres=# SELECT * FROM sauna;
 seat | status
------+--------
    1 | ×
    2 | ○
    3 | ○
    4 | ○
    5 | ×
    6 | ×
    7 | ○
    8 | ○
    9 | ○
   10 | ×
   11 | ×
   12 | ×
   13 | ○
   14 | ×
   15 | ×
```

`×`が既に座られている席、`○`は空いている席です

このから座れる席は、
* 2, 3
* 3, 4
* 7, 8
* 8, 9

になるのでこれをSQLで求めます。

## NOT EXISTSを使用する

以下が、欲しい条件から出力されたものです

```
 start_seat | end_seat
------------+----------
          5 |        6
         10 |       11
         11 |       12
         14 |       15
```

ここで必要な情報は、
**「始点`n ~ n+([座る人数(今回は2)] - 1)`までの全ての席が`○`である事」** です

そのためにまず、始点と終点の組み合わせを作ります

### 始点と終点の組み合わせを作る

```sql
SELECT S1.seat AS start_seat, S2.seat AS end_seat
FROM sauna S1, sauna S2
WHERE S2.seat = S1.seat + (2-1);
```

```
 start_seat | end_seat
------------+----------
          1 |        2
          2 |        3
          3 |        4
          4 |        5
          5 |        6
          6 |        7
          7 |        8
          8 |        9
          9 |       10
         10 |       11
         11 |       12
         12 |       13
         13 |       14
         14 |       15
```

始点~終点までが2席になる組み合わせを作成しました

続いて、連続した2席が`○`の席に絞ります

### 始点から終点の全ての席が空いている条件を追加

全ての席が`○`を二重否定にして、**`×`ではない席が存在しない** として記述します。
ここで、`NOT EXISTS`を使用します

そして、始点と終点の範囲として`BETWEEN`を使用します

### 結果がこちら

```sql
SELECT S1.seat AS start_seat, S2.seat AS end_seat
FROM sauna S1, sauna S2
WHERE S2.seat = S1.seat + (2-1)
AND NOT EXISTS (
    SELECT * 
    FROM sauna S3
    WHERE S3.seat
    BETWEEN S1.seat AND S2.seat AND S3.status <> '×'
);
```

```
 start_seat | end_seat
------------+----------
          5 |        6
         10 |       11
         11 |       12
         14 |       15
```

## ウィンドウ関数の場合

結果は以下のようになります

```sql
SELECT seat, seat + (2-1) AS end_seat
FROM (
    SELECT seat, MAX(seat)
    OVER(
        ORDER BY seat ROWS BETWEEN (2-1) FOLLOWING AND (2-1) FOLLOWING
    ) AS end_seat
    FROM sauna WHERE status = '○'
) TMP
WHERE end_seat - seat = (2-1);
```

```
 seat | end_seat
------+----------
    2 |        3
    3 |        4
    7 |        8
    8 |        9
```

分解して考えてみます

### 空席の場合に絞り、ウィンドウ関数で次席を求める

```sql
SELECT seat, MAX(seat)
OVER(
    ORDER BY seat ROWS BETWEEN (2-1) FOLLOWING AND (2-1) FOLLOWING
) AS end_seat
FROM sauna WHERE status = '○';
```

```
 seat | end_seat
------+----------
    2 |        3
    3 |        4
    4 |        7
    7 |        8
    8 |        9
    9 |       13
   13 |
```

連続した2席を出す場合、ここから1つ後ろの席が分かれば回答を出すことが出来ます

さらに、以下の条件を追加することで求める事ができます
`WHERE end_seat - seat = (2-1);`

# 複数段のサウナの場合

(大概が階段状になっていますが）

![スクリーンショット 2023-01-07 12.17.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/536974/c77004b6-a19e-42c2-94dd-48c8d95d3ca6.png)

以下のような座席の配置になっていると仮定します

![スクリーンショット 2023-01-07 15.52.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/536974/bc2bf86d-382e-42d0-1755-e0d715a782fa.png)

この場合、2人が隣り合う席は
* 2, 3
* 13, 14

の2パターンになります。
5, 6や、10, 11は隣り合わないので除外する様にします

## 列を判別するためのline_idを含んだテーブルを作成

```sql
CREATE TABLE sauna
 ( seat   INTEGER NOT NULL  PRIMARY KEY,
   line_id CHAR(1) NOT NULL,
   status CHAR(2) NOT NULL
     CHECK (status IN ('○', '×')) );

INSERT INTO sauna VALUES (1, 'A', '×');
INSERT INTO sauna VALUES (2, 'A', '○');
INSERT INTO sauna VALUES (3, 'A', '○');
INSERT INTO sauna VALUES (4, 'A', '×');
INSERT INTO sauna VALUES (5, 'A', '○');
INSERT INTO sauna VALUES (6, 'B', '○');
INSERT INTO sauna VALUES (7, 'B', '×');
INSERT INTO sauna VALUES (8, 'B', '○');
INSERT INTO sauna VALUES (9, 'B', '×');
INSERT INTO sauna VALUES (10,'B', '○');
INSERT INTO sauna VALUES (11,'C', '○');
INSERT INTO sauna VALUES (12,'C', '×');
INSERT INTO sauna VALUES (13,'C', '○');
INSERT INTO sauna VALUES (14,'C', '○');
INSERT INTO sauna VALUES (15,'C', '×');
```

```
 seat | line_id | status
------+---------+--------
    1 | A       | ×
    2 | A       | ○
    3 | A       | ○
    4 | A       | ×
    5 | A       | ○
    6 | B       | ○
    7 | B       | ×
    8 | B       | ○
    9 | B       | ×
   10 | B       | ○
   11 | C       | ○
   12 | C       | ×
   13 | C       | ○
   14 | C       | ○
   15 | C       | ×
```

## NOT EXISTSを使用する場合

```sql
SELECT S1.seat AS start_seat, S2.seat AS end_seat
FROM sauna S1, sauna S2
WHERE S2.seat = S1.seat + (2-1)
AND NOT EXISTS (
    SELECT * FROM sauna S3
    WHERE S3.seat
    BETWEEN S1.seat AND S2.seat AND (
        S3.status <> '○' OR S3.line_id <> S1.line_id
    )
);
```

```
 start_seat | end_seat
------------+----------
          2 |        3
         13 |       14
```

1列のみだった時と異なるのは以下の点です。

列を判別するための条件を追加しました。

```sql
+ OR S3.line_id <> S1.line_id
```

## ウィンドウ関数を使用した場合

```sql
SELECT seat, seat + (2-1) AS end_seat
FROM (
    SELECT seat, MAX(seat)
    OVER(
        PARTITION BY line_id ROWS BETWEEN (2-1) FOLLOWING AND (2-1) FOLLOWING
    ) AS end_seat
    FROM sauna WHERE status = '○'
) TMP
WHERE end_seat - seat = (2-1);
```

```
 seat | end_seat
------+----------
    2 |        3
   13 |       14
```

複数段になった場合は`PARTITION BY`を使用してline_idをキーに部分集合を作ります
変更箇所は以下です

```
- ORDER BY seat
+ PARTITION BY line_id
```

# 参考

https://www.amazon.co.jp/%E9%81%94%E4%BA%BA%E3%81%AB%E5%AD%A6%E3%81%B6SQL%E5%BE%B9%E5%BA%95%E6%8C%87%E5%8D%97%E6%9B%B8-%E7%AC%AC2%E7%89%88-%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E7%B5%82%E3%82%8F%E3%82%8A%E3%81%9F%E3%81%8F%E3%81%AA%E3%81%84%E3%81%82%E3%81%AA%E3%81%9F%E3%81%B8-CodeZine-BOOKS/dp/4798157821