#時間帯の重複を抽出したい

Question

前提・実現したいこと

pythonでこのようなdataframeがあります。

日付　入店時間　退店時間　席番号
12 13:00 14:00 3
12 13:15 13:30 4
12 13:30 13:45 3
... ... ... ...

この中から、同じ席番号に滞在しているにもかかわらず
滞在時間帯が被ってしまっている行（上の場合、3行目）を抽出したいです。

発生している問題・エラーメッセージ

現在のソースコードだと
処理が永遠に終わりません。。。
このような場合、どのようなコードがいいのか
教えていただきたいです

エラーメッセージ

該当のソースコード

for i in range(len(df)):
 for j in range(i+1,len(df)):
   if df.iloc[i,3] == df.iloc[j,3]:
     if df.iloc[i,1] < df.iloc[j,1] <df.iloc[i,2]:
        tmp = df.iloc[j,:]
        df_dup = df_dup.append(tmp)

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

面白そうなのでやってみました。
縦軸を時間、横軸を客(index)として１分ごとのタイムテーブルを作成して、同時刻に同じ席に２人以上のデータがないかを確認しています。

比較演算がないので、データがメモリに乗りさえすればそれほど遅くならないかと思います。

タイムテーブルはとりあえず１分ごとにしておりますが、データによってはもう間引くことができるのではないでしょうか。

また結果の出力形式はあまり考えずに、重複した箇所を全部出力しておりますが、あとはDataFrameを変換するだけなのでどうにでもなるかと思います。

import pandas as pd

df = pd.DataFrame([[12,'13:00','14:00',3],
                   [12,'13:15','13:30',4],
                   [12,'13:30','13:45',3],
                   [12,'13:35','15:00',4],
                   [12,'14:55','15:00',4]],
                  columns=['日付','入店時間','退店時間','席番号'])

df['入店時間'] = pd.to_datetime(df['入店時間'])
df['退店時間'] = pd.to_datetime(df['退店時間'])

# 日付ごとに処理
for day, day_df in df.groupby('日付'):
    lst = []
    for idx, row in day_df.iterrows():
        lst.append(pd.Series(row['席番号'], index = pd.date_range(row['入店時間'], row['退店時間'], freq='1min')))
    # 日付を表示
    print("{}日".format(idx))
    # タイムテーブルを生成
    time_table = pd.concat(lst, axis=1)
    time_table.index = time_table.index.strftime('%H:%M')
    # 重複がある時間のみ抽出
    time_table = time_table[(time_table.apply(pd.value_counts, axis=1)>1.0).any(axis=1)]
    # 重複があるデータ以外は削除
    time_table = time_table.apply(lambda d: d[d.duplicated(keep=False) & d.notna()], axis=1)
    print(time_table)

#4日
#         0    2    3    4
#13:30  3.0  3.0  NaN  NaN
#13:31  3.0  3.0  NaN  NaN
#13:32  3.0  3.0  NaN  NaN
#13:33  3.0  3.0  NaN  NaN
#13:34  3.0  3.0  NaN  NaN
#13:35  3.0  3.0  NaN  NaN
#13:36  3.0  3.0  NaN  NaN
#13:37  3.0  3.0  NaN  NaN
#13:38  3.0  3.0  NaN  NaN
#13:39  3.0  3.0  NaN  NaN
#13:40  3.0  3.0  NaN  NaN
#13:41  3.0  3.0  NaN  NaN
#13:42  3.0  3.0  NaN  NaN
#13:43  3.0  3.0  NaN  NaN
#13:44  3.0  3.0  NaN  NaN
#13:45  3.0  3.0  NaN  NaN
#14:55  NaN  NaN  4.0  4.0
#14:56  NaN  NaN  4.0  4.0
#14:57  NaN  NaN  4.0  4.0
#14:58  NaN  NaN  4.0  4.0
#14:59  NaN  NaN  4.0  4.0
#15:00  NaN  NaN  4.0  4.0

Answer 2

コードを書くのが面倒なので、疑似コードを。

while リスト中のデータがなくなるまで繰り返す
  一番初めのデータを取得する(1)
  (1)のデータに重複するデータをリストから取得する(2)
  (1)と(2)をセットにして保持する
  (1)と(2)のデータをリストから削除する

こんな感じで、セットをため込みます。
これで、重複するデータが得られるはずです。