如何在DataFrame中用无重叠区间替换重叠区间？

问题描述 #

需要清理一个包含时间区间的DataFrame，消除所有重叠区间。原始DataFrame结构如下：

start    end     speaker
0   0.03   0.33  SPEAKER_02
1   1.24   6.91  SPEAKER_02
2   1.38   2.03  SPEAKER_00
3   7.11   9.64  SPEAKER_02
4   9.80  21.02  SPEAKER_02
5  15.37  15.52  SPEAKER_01
6  16.55  16.80  SPEAKER_00
7  21.36  26.40  SPEAKER_02
8  26.76  27.01  SPEAKER_02

重叠处理规则：当区间重叠时，拆分出无重叠的新行，子区间（完全包含在长区间内的区间）的speaker优先覆盖长区间的对应部分。例如：

• 原第1、2行需拆分为3行无重叠区间：

  1   1.24   1.37  SPEAKER_02
  2   1.38   2.03  SPEAKER_00
  3   2.04   6.91  SPEAKER_02
  

• 原第4、5、6行需拆分为4行无重叠区间：

  4   9.80  15.36  SPEAKER_02
  5  15.37  15.52  SPEAKER_01
  6  15.53  16.54  SPEAKER_02
  7  16.55  16.80  SPEAKER_00
  

核心要求：数据量极大，方案必须高效，避免低效的自定义循环。

高效解决方案 #

采用事件驱动+栈维护的方法，时间复杂度为O(n log n)，适合大数据量处理：

import pandas as pd

# 初始化原始DataFrame
df = pd.DataFrame({
    'start': [0.03, 1.24, 1.38, 7.11, 9.80, 15.37, 16.55, 21.36, 26.76],
    'end': [0.33, 6.91, 2.03, 9.64, 21.02, 15.52, 16.80, 26.40, 27.01],
    'speaker': ['SPEAKER_02', 'SPEAKER_02', 'SPEAKER_00', 'SPEAKER_02', 'SPEAKER_02', 'SPEAKER_01', 'SPEAKER_00', 'SPEAKER_02', 'SPEAKER_02']
})

# 生成事件列表：(时间, 事件类型, speaker)
# enter表示进入区间，exit表示离开区间（离开时间设为end+0.01，确保区间无重叠）
events = []
for _, row in df.iterrows():
    events.append((row['start'], 'enter', row['speaker']))
    events.append((row['end'] + 0.01, 'exit', row['speaker']))

# 排序事件：按时间升序，同时间时exit事件优先（避免同一时间点的重叠）
events.sort(key=lambda x: (x[0], 0 if x[1] == 'exit' else 1))

# 遍历事件生成无重叠区间
result = []
current_time = None
speaker_stack = []
current_speaker = None

for time, event_type, speaker in events:
    # 生成当前时间到事件时间的区间（如果有间隔）
    if current_time is not None and time > current_time:
        result.append({
            'start': round(current_time, 2),
            'end': round(time - 0.01, 2),
            'speaker': current_speaker
        })
    # 更新speaker栈
    if event_type == 'enter':
        speaker_stack.append(speaker)
        current_speaker = speaker_stack[-1]
    else:
        # 弹出对应的speaker，处理嵌套场景
        try:
            speaker_stack.remove(speaker)
        except ValueError:
            pass
        current_speaker = speaker_stack[-1] if speaker_stack else None
    current_time = time

# 转换为结果DataFrame
result_df = pd.DataFrame(result)
print(result_df)

方案说明 #

1. 事件生成：将每个区间拆分为「进入」和「离开」两个事件，离开时间设为原区间end+0.01，保证区间左闭右闭且无重叠。
2. 事件排序：按时间排序，同时间的离开事件优先，避免出现同一时间点先进入后离开导致的逻辑错误。
3. 栈维护speaker：用栈记录当前活跃的speaker，子区间的进入事件会压入栈顶，优先使用；离开事件弹出对应speaker，自动恢复到父区间的speaker。
4. 区间生成：遍历事件时，根据相邻事件的时间差生成无重叠的区间，确保覆盖所有原始时间范围。

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