求助：基于时间区间高效标记Pandas父子节点的Pythonic方案

给定包含时间区间（start/end）的DataFrame，我们需要为每个区间找到直接父区间（即最小的包含当前区间的区间）。原O(N²)的循环方案效率较低，以下是两种高效实现方案：

方案一：基于栈的贪心算法（时间复杂度O(N log N)） #

这是处理区间嵌套问题的经典解法，核心是通过排序和栈来追踪区间层级：

import pandas as pd

df = pd.DataFrame([[1, 12], [4, 9], [6, 7], [10, 11]],
                  index=['A', 'B', 'C', 'D'],
                  columns=['start', 'end'])

# 按start升序、end降序排序：确保先处理左边界小、右边界大的区间
df_sorted = df.sort_values(by=['start', 'end'], ascending=[True, False]).copy()

stack = []
parent_map = {}

for idx, row in df_sorted.iterrows():
    # 弹出栈中所有无法包含当前区间的元素（右边界<=当前区间右边界）
    while stack and stack[-1][1] <= row['end']:
        stack.pop()
    # 栈顶就是直接父区间，栈空则父为自身（或替换为pd.NA）
    parent_map[idx] = stack[-1][0] if stack else idx
    # 将当前区间压入栈，维护嵌套层级
    stack.append((idx, row['end']))

# 将父节点映射回原DataFrame
df['parent'] = df.index.map(parent_map)

print(df)

原理说明： #

排序后，栈中始终维护着当前未被完全包含的区间。遍历每个区间时，先移除栈中所有右边界小于等于当前区间的元素（这些区间无法包含当前区间），剩下的栈顶元素就是能包含当前区间的最小区间（直接父）。整个过程每个元素仅入栈和出栈一次，加上排序的O(N log N)，整体效率远高于O(N²)。

方案二：利用pandas IntervalIndex实现向量化匹配 #

借助pandas的IntervalIndex可以快速完成区间包含关系的判断，避免显式循环：

import pandas as pd

df = pd.DataFrame([[1, 12], [4, 9], [6, 7], [10, 11]],
                  index=['A', 'B', 'C', 'D'],
                  columns=['start', 'end'])

# 创建闭合区间的IntervalIndex
intervals = pd.IntervalIndex.from_arrays(df['start'], df['end'], closed='both')

def find_parent(idx):
    current_interval = intervals[idx]
    # 筛选出所有包含当前区间的区间（排除自身）
    mask = intervals.contains(current_interval)
    mask[idx] = False
    if not mask.any():
        return idx  # 无父区间时返回自身，可替换为pd.NA
    # 在包含区间中选start最大的（即最内层的直接父区间）
    candidates = df[mask]
    return candidates.index[candidates['start'].idxmax()]

# 映射得到每个区间的父节点
df['parent'] = df.index.map(find_parent)

print(df)

原理说明： #

IntervalIndex的contains方法是向量化操作，比逐行循环快得多。找到所有包含当前区间的候选后，选择start最大的那个——因为start越大，区间的左边界越靠近当前区间，意味着它是最内层的包含区间（直接父节点）。

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