本文介绍一种贪心策略，为 pandas dataframe 中的每一行分配组号，确保每组内 timestamp1 和 timestamp2 的极差（max - min）均不超过 4 天，且组内行数最大化。
本文介绍一种贪心策略，为 pandas dataframe 中的每一行分配组号，确保每组内 timestamp1 和 timestamp2 的极差（max - min）均不超过 4 天，且组内行数最大化。
在实际数据分析中，常需将时间序列数据按“局部紧凑性”划分逻辑组，而非简单按固定周期（如周/月）切分。本例要求：每个组必须同时满足两个独立的时间跨度约束——
- 组内 timestamp1 的最大值与最小值之差 ≤ 4 天；
- 组内 timestamp2 的最大值与最小值之差 ≤ 4 天。
注意：这不是聚类问题（无需全局优化），而是典型的在线贪心分组（online greedy grouping）：按原始顺序遍历行，只要当前行加入现有组会导致任一时间列超限，就新建组，并以该行为新组的起始锚点（记录其 timestamp1 和 timestamp2 作为后续比较基准）。
以下为完整实现：
import pandas as pd
# 构造示例数据
data = {
'timestamp1': ['2022-02-18', '2022-02-19', '2022-02-21', '2022-03-11', '2022-03-12', '2022-03-30'],
'timestamp2': ['2023-01-02', '2023-01-04', '2023-01-11', '2024-02-05', '2024-02-06', '2024-02-07']
}
df = pd.DataFrame(data)
df['timestamp1'] = pd.to_datetime(df['timestamp1'])
df['timestamp2'] = pd.to_datetime(df['timestamp2'])
def assign_groups_greedy(df):
"""贪心分组：维护当前组的 timestamp1_min 和 timestamp2_min，逐行判断是否可加入"""
if df.empty:
return []
groups = []
current_group = 1
# 初始化首行为第一组的基准
start_t1 = df.iloc[0]['timestamp1']
start_t2 = df.iloc[0]['timestamp2']
for _, row in df.iterrows():
# 检查当前行是否违反任一约束
t1_violated = (row['timestamp1'] - start_t1).days > 4
t2_violated = (row['timestamp2'] - start_t2).days > 4
if t1_violated or t2_violated:
current_group += 1
# 更新基准为当前行（新组起点）
start_t1 = row['timestamp1']
start_t2 = row['timestamp2']
groups.append(current_group)
return groups
df['group'] = assign_groups_greedy(df)
print(df)
输出结果符合预期：
timestamp1 timestamp2 group 0 2022-02-18 2023-01-02 1 1 2022-02-19 2023-01-04 1 2 2022-02-21 2023-01-11 2 # 因 timestamp2 超出 2023-01-02+4d=2023-01-06 3 2022-03-11 2024-02-05 3 # timestamp1 已距 group2 起点超 4d，另起一组 4 2022-03-12 2024-02-06 3 5 2022-03-30 2024-02-07 4 # timestamp1 距 group3 起点（2022-03-11）达 19d > 4d
⚠️ 关键注意事项：
- 顺序敏感性：该算法依赖输入行序。若需更鲁棒的分组（如不依赖原始顺序），应先按 timestamp1 或 timestamp2 排序（推荐双排序：df.sort_values(['timestamp1', 'timestamp2'])），否则可能产生次优分组；
- 边界定义：“≤ 4 天”指日历天数差（.days），非工作日；若需排除周末/节假日，需配合 pd.bdate_range 或自定义日历；
- 扩展性：若约束变为“任意两行间时间差 ≤ 4 天”（即全连接约束），则属 NP-hard 区间图着色问题，需改用图算法或启发式；本文的贪心法仅保证 连续锚定 下的局部最优，但实践中高效且可解释性强；
- 性能优化：对超大数据集（>10⁶ 行），可用 numba.jit 加速循环，或改用 itertools.groupby 配合预计算差值数组。
此方法平衡了逻辑清晰性、实现简洁性与工程实用性，是处理多维时间窗口分组任务的可靠基线方案。
