高效删除重叠区间行：寻求Pandas内置函数优化实现方案

问题说明 #

原始DataFrame如下：

>>> df
   Start  End  Tiebreak
0      1    6  0.376600
1      5    7  0.050042
2     15   20  0.628266
3     10   15  0.984022
4     11   12  0.909033
5      4    8  0.531054

需求：当两行的[Start, End]区间存在重叠时，删除其中Tiebreak值较低的行。处理后的预期结果为：

>>> df
   Start  End  Tiebreak
2     15   20  0.628266
3     10   15  0.984022
5      4    8  0.531054

当前采用双循环实现逻辑，但数据量大时效率极低，需要基于Pandas内置函数的高效实现方案。

现有低效双循环实现 #

import pandas as pd
import numpy as np

# 初始化数据
df = pd.DataFrame({
    'Start': [1, 5, 15, 10, 11, 4],
    'End': [6, 7, 20, 15, 12, 8],
    'Tiebreak': np.random.uniform(0, 1, 6)
})

# 检查重叠并删除低权重行
list_idx_drop = []
for i in range(len(df) - 1):
    for j in range(i + 1, len(df)):
        idx_1 = df.index[i]
        idx_2 = df.index[j]

        cond_1 = (df.loc[idx_1, 'Start'] < df.loc[idx_2, 'End'])
        cond_2 = (df.loc[idx_2, 'Start'] < df.loc[idx_1, 'End'])
        
        # 区间重叠时
        if cond_1 & cond_2:
            tie_1 = df.loc[idx_1, 'Tiebreak']
            tie_2 = df.loc[idx_2, 'Tiebreak']

            # 删除Tiebreak值较低的行
            if tie_1 < tie_2:  
                df.drop(idx_1, inplace=True)
            else:
                df.drop(idx_2, inplace=True)

高效实现方案 #

核心思路是先按Tiebreak降序排序，确保高权重行优先被保留；再通过一次遍历，只保留与已保留区间不重叠的行，时间复杂度为O(n log n)（主要来自排序），远优于双循环的O(n²)。

代码实现：

import pandas as pd
import numpy as np

# 原始数据
df = pd.DataFrame({
    'Start': [1, 5, 15, 10, 11, 4],
    'End': [6, 7, 20, 15, 12, 8],
    'Tiebreak': [0.376600, 0.050042, 0.628266, 0.984022, 0.909033, 0.531054]
})

# 按Tiebreak降序排序，优先处理高权重行
sorted_df = df.sort_values('Tiebreak', ascending=False).reset_index(drop=True)

# 初始化保留列表和最后保留区间的结束值
keep_rows = []
last_kept_end = -float('inf')

for _, row in sorted_df.iterrows():
    # 当前区间与已保留区间无重叠，则保留
    if row['Start'] >= last_kept_end:
        keep_rows.append(row)
        last_kept_end = row['End']

# 转换为DataFrame，可按Start排序恢复有序性
result = pd.DataFrame(keep_rows).sort_values('Start').reset_index(drop=True)
print(result)

运行后输出与预期结果一致，且数据量越大，效率提升越明显。

内容的提问来源于stack exchange，提问作者clueless