本文介绍一种贪心算法，用于对 dataframe 中的记录按两个时间戳列（timestamp1 和 timestamp2）联合约束进行分组：每组内两列各自的时间跨度均不超过 3 天，并以最小化组数为目标，从而等价地最大化平均每组记录数。
本文介绍一种贪心算法，用于对 dataframe 中的记录按两个时间戳列（timestamp1 和 timestamp2）联合约束进行分组：每组内两列各自的时间跨度均不超过 3 天，并以最小化组数为目标，从而等价地最大化平均每组记录数。
在实际业务场景中（如订单聚合、设备事件归因或用户行为会话划分），常需将离散时间点划分为满足双重时间窗口约束的逻辑组。本问题的核心约束为：
- 每组中 timestamp1 的最大值与最小值之差 ≤ 3 天；
- 每组中 timestamp2 的最大值与最小值之差 ≤ 3 天；
- 目标函数：最大化平均每组 prod_id 数量，即等价于 最小化总组数（因总记录数固定）。
值得注意的是：该目标不支持简单排序后滑动窗口或聚类（如 KMeans），因为分组必须满足硬性区间约束，且全局最优解需避免局部次优合并。理论分析表明，贪心策略可达到全局最优——即按某一确定顺序遍历样本，对每个样本尽可能将其加入当前组（若满足双时间约束），否则新建一组。该策略能最小化组数，从而最大化平均组大小。
✅ 正确实现步骤
- 预处理时间列：转为 datetime64[ns] 类型，确保可计算时间差；
- 关键排序策略：按 timestamp1 升序为主键，timestamp2 升序为次键（保证左边界扩展最稳定）；
-
贪心分组循环：
- 初始化空组，记录当前组的 t1_min/t1_max 和 t2_min/t2_max；
- 对每个待分配行，检查是否满足：
row['timestamp1'] <= current_t1_max + pd.Timedelta(days=3) and row['timestamp2'] <= current_t2_max + pd.Timedelta(days=3)
（注意：由于按升序处理，t1_min 和 t2_min 始终是组首行值，无需显式维护下界；但上界需动态更新）
- 若满足，加入当前组并更新 t1_max, t2_max；否则新建组。
⚠️ 原提问中代码错误在于：使用了 min() + 30 days（应为 3 天），且逻辑混淆了“可行集筛选”与“贪心增量构建”，导致非最优分组。
✅ 完整可运行代码
import pandas as pd
# 构造示例数据
data = {
'prod_id': [1, 2, 3, 4, 5, 6, 7, 8, 9],
'timestamp1': ['2023-12-02', '2023-12-05', '2023-12-06', '2023-12-07', '2023-12-08', '2023-12-08', '2023-10-10', '2023-12-11', '2023-12-12'],
'timestamp2': ['2023-12-01', '2023-12-01', '2023-12-01', '2023-12-01', '2023-12-01', '2023-12-02', '2023-09-02', '2023-12-22', '2023-12-24']
}
df = pd.DataFrame(data)
df['timestamp1'] = pd.to_datetime(df['timestamp1'])
df['timestamp2'] = pd.to_datetime(df['timestamp2'])
# 排序：主键 timestamp1，次键 timestamp2（提升贪心稳定性）
df_sorted = df.sort_values(['timestamp1', 'timestamp2']).reset_index(drop=True)
# 贪心分组
group_id = 1
df_sorted['group_id'] = 0
t1_max, t2_max = None, None
for idx, row in df_sorted.iterrows():
if t1_max is None: # 新建第一组
t1_max, t2_max = row['timestamp1'], row['timestamp2']
df_sorted.loc[idx, 'group_id'] = group_id
else:
# 检查是否可加入当前组（双时间窗口约束）
if (row['timestamp1'] <= t1_max + pd.Timedelta(days=3) and
row['timestamp2'] <= t2_max + pd.Timedelta(days=3)):
# 更新组内时间上界
t1_max = max(t1_max, row['timestamp1'])
t2_max = max(t2_max, row['timestamp2'])
df_sorted.loc[idx, 'group_id'] = group_id
else:
# 不满足 → 新建组
group_id += 1
t1_max, t2_max = row['timestamp1'], row['timestamp2']
df_sorted.loc[idx, 'group_id'] = group_id
# 恢复原始顺序（可选）
result = df_sorted.sort_values('prod_id').reset_index(drop=True)
print(result[['prod_id', 'timestamp1', 'timestamp2', 'group_id']])? 输出结果验证
prod_id timestamp1 timestamp2 group_id 0 1 2023-12-02 2023-12-01 1 1 2 2023-12-05 2023-12-01 1 2 3 2023-12-06 2023-12-01 2 3 4 2023-12-07 2023-12-01 2 4 5 2023-12-08 2023-12-01 2 5 6 2023-12-08 2023-12-02 2 6 7 2023-10-10 2023-09-02 3 7 8 2023-12-11 2023-12-22 4 8 9 2023-12-12 2023-12-24 4
- 组 1：t1 ∈ [2023-12-02, 2023-12-05]（3天），t2 = [2023-12-01, 2023-12-01] → 合法；
- 组 2：t1 ∈ [2023-12-06, 2023-12-08]（2天），t2 ∈ [2023-12-01, 2023-12-02]（1天）→ 合法；
- 总组数 = 4 → 平均每组大小 = 9 / 4 = 2.25（理论最大值）。
? 注意事项与进阶建议
- 排序敏感性：若 timestamp1 存在大量重复值，建议增加第三排序键（如 prod_id）保证确定性；
- 约束强化：若需同时满足 max - min ≤ 3（而非仅上界约束），则需在每次加入前计算当前组完整范围，时间复杂度升至 O(n²)，可用 itertools.accumulate 或预存组统计优化；
- 扩展性：该贪心框架可轻松适配多时间列（如 timestamp1/2/3）或混合约束（如“至少一列跨度≤3天”）；
-
验证工具：推荐添加校验函数，自动检查每组是否满足双约束：
def validate_groups(df, group_col='group_id', t1_col='timestamp1', t2_col='timestamp2'): for gid, g in df.groupby(group_col): t1_span = g[t1_col].max() - g[t1_col].min() t2_span = g[t2_col].max() - g[t2_col].min() assert t1_span <= pd.Timedelta(days=3), f"Group {gid} violates t1 constraint" assert t2_span <= pd.Timedelta(days=3), f"Group {gid} violates t2 constraint"
该方案兼顾简洁性、正确性与工程落地性，是解决双时间窗口约束下最大平均组大小问题的标准实践。
