Immediate Food Delivery II

アルゴリズム概要

問題の説明

食品配達サービスにおいて、各顧客の最初の注文が即日配達（order_date = customer_pref_delivery_date）だった割合を求めます。 即日配達の場合は「immediate」、予約配達の場合は「scheduled」として分類されます。

入力例

Delivery table:
+-------------+-------------+------------+-----------------------------+
| delivery_id | customer_id | order_date | customer_pref_delivery_date |
+-------------+-------------+------------+-----------------------------+
| 1           | 1           | 2019-08-01 | 2019-08-02                  |
| 2           | 2           | 2019-08-02 | 2019-08-02                  |
| 3           | 1           | 2019-08-11 | 2019-08-12                  |
| 4           | 3           | 2019-08-24 | 2019-08-24                  |
| 5           | 3           | 2019-08-21 | 2019-08-22                  |
| 6           | 2           | 2019-08-11 | 2019-08-13                  |
| 7           | 4           | 2019-08-09 | 2019-08-09                  |
+-------------+-------------+------------+-----------------------------+

出力例

+----------------------+
| immediate_percentage |
+----------------------+
| 50.00                |
+----------------------+

制約条件

• delivery_id は主キー（重複なし）
• 各顧客は必ず1つ以上の注文を持つ
• customer_pref_delivery_date は order_date 以降の日付
• 結果は小数点2桁で四捨五入

解法戦略

主要ポイント

• 時間計算量: O(N log N) - グループ内ソートが必要
• 空間計算量: O(顧客数) - 最初の注文のみ保持
• 最適化: ウィンドウ関数を使用して1パスで処理

ステップバイステップ解説

実装コード

PostgreSQL 16.6+ 実装

WITH first_orders AS (
  SELECT
    customer_id,
    order_date,
    customer_pref_delivery_date,
    ROW_NUMBER() OVER (
      PARTITION BY customer_id
      ORDER BY order_date
    ) AS rn
  FROM Delivery
)
SELECT
  ROUND(
    100.0 * SUM(CASE WHEN order_date = customer_pref_delivery_date THEN 1 ELSE 0 END)
    / COUNT(*),
    2
  ) AS immediate_percentage
FROM first_orders
WHERE rn = 1;

Python (Pandas 2.2.2) 実装

import pandas as pd

def immediate_food_delivery(delivery: pd.DataFrame) -> pd.DataFrame:
    """
    各顧客の最初の注文における即日配達の割合を計算

    Args:
        delivery: 配達情報 (delivery_id, customer_id, order_date, customer_pref_delivery_date)

    Returns:
        pd.DataFrame: 列名は ['immediate_percentage']、1行のみ
    """
    # 各顧客の最初の注文（order_dateが最小）のインデックスを取得
    first_order_idx = delivery.groupby('customer_id')['order_date'].idxmin()

    # 最初の注文のみを抽出
    first_orders = delivery.loc[first_order_idx, ['order_date', 'customer_pref_delivery_date']]

    # 即日配達判定（order_date == customer_pref_delivery_date）
    is_immediate = (first_orders['order_date'] == first_orders['customer_pref_delivery_date'])

    # 割合を計算（パーセンテージ、小数点2桁）
    percentage = round(100.0 * is_immediate.sum() / len(is_immediate), 2)

    return pd.DataFrame({'immediate_percentage': [percentage]})

処理フローチャート

計算量分析

詳細説明