给定区间空白分配优化：基于Pandas DataFrame的最优实现问询

问题背景 #

总区间范围：start = 87.5，end = 107.5
当前已分配的子区间如下：

现在需要插入一个长度为X = 0.3的新区间，要求不新增空白、提升区间紧凑度——也就是最大化利用现有间隙，避免分散排布，以便后续容纳更多同长度的区间。

最优解逻辑 #

核心思路是优先填充现有间隙中，插入后剩余空间最小的位置（或直接紧贴已有区间的间隙端点），这样既不会产生新空白，还能让所有区间尽可能集中，提升整体紧凑度：

1. 计算总区间内所有未被占用的间隙（包括总区间首尾到第一个/最后一个子区间的空隙，以及相邻子区间之间的空隙）
2. 筛选出长度≥X的可用间隙
3. 选择最适合的位置插入：优先紧贴已有区间的右端或左端，保证区间的连续性，避免间隙碎片化

Pandas实现步骤 #

1. 加载现有数据到DataFrame #

import pandas as pd

# 现有分配数据
data = {
    'lower': [87.85, 89.75, 91.45, 96.05, 96.85, 98.85, 100.85, 101.9, 102.9, 105.35, 107.81],
    'upper': [88.15, 90.05, 91.75, 96.35, 97.15, 99.15, 101.15, 102.1, 103.1, 105.65, 107.99]
}
df = pd.DataFrame(data)

2. 计算所有可用间隙 #

遍历计算总区间内的所有空白间隙：

X = 0.3
total_start = 87.5
total_end = 107.5

gaps = []
# 总区间起始到第一个子区间的间隙
first_gap = {
    'start': total_start,
    'end': df['lower'].iloc[0],
    'length': df['lower'].iloc[0] - total_start
}
gaps.append(first_gap)

# 相邻子区间之间的间隙
for i in range(1, len(df)):
    gap_start = df['upper'].iloc[i-1]
    gap_end = df['lower'].iloc[i]
    gaps.append({
        'start': gap_start,
        'end': gap_end,
        'length': gap_end - gap_start
    })

# 最后一个子区间到总区间结束的间隙
last_gap = {
    'start': df['upper'].iloc[-1],
    'end': total_end,
    'length': total_end - df['upper'].iloc[-1]
}
gaps.append(last_gap)

# 转成DataFrame便于筛选
gaps_df = pd.DataFrame(gaps)

3. 筛选最优插入位置 #

筛选出能容纳X的间隙，优先选择紧贴已有区间的位置（即间隙起始点为某子区间的右端）：

# 筛选长度≥X的间隙
valid_gaps = gaps_df[gaps_df['length'] >= X]

# 优先选择从已有区间右端开始的间隙（保证紧凑性）
# 如果没有这类间隙，再选择剩余空间最小的间隙
best_gap = valid_gaps[valid_gaps['start'].isin(df['upper'])].iloc[0] if not valid_gaps[valid_gaps['start'].isin(df['upper'])].empty else valid_gaps.sort_values('length').iloc[0]

# 生成新区间：从间隙起始位置开始，长度为X
new_lower = best_gap['start']
new_upper = best_gap['start'] + X

4. 插入新区间并排序 #

# 添加新区间到原DataFrame
new_row = pd.DataFrame({'lower': [new_lower], 'upper': [new_upper]})
updated_df = pd.concat([df, new_row], ignore_index=True)

# 按lower列重新排序，保证区间顺序正确
updated_df = updated_df.sort_values('lower').reset_index(drop=True)

最终结果 #

按上述逻辑插入后的区间如下（新增区间已加粗）：

此方案相比示例中的88.55-88.85更优，因为它直接紧贴已有区间，避免了间隙碎片化，最大化保证了紧凑性。

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