如何高效按预定义时间段统计在世人员数量？

你要统计的是与预定义时间段存在时间交集的人数（只要在世时间和目标时段有重叠就算），不用靠大量条件判断的循环，用「排序+二分查找」就能高效解决，数据量越大优势越明显。

方法一：排序+二分查找（最适配你的需求） #

核心逻辑 #

一个人会被计入某个时间段 [T_start, T_end]，当且仅当：

他的出生年份 < T_end 并且 死亡年份 > T_start

只要满足这两个条件，就说明他在世的时间和目标时段有重叠，符合统计要求。

具体步骤 #

1. 提取并排序数据：把所有人的出生年份、死亡年份分别提取出来，各自排序成数组。
   比如你的示例数据处理后：

   出生年份数组（排序后）：[1920, 1930, 1960, 1960]
   死亡年份数组（排序后）：[1950, 1950, 1970, 2020]
   

2. 二分查找快速计算：对每个预定义时间段，用二分查找快速统计两个关键数值：
   • 「出生年份 < T_end」的人数：用二分找到第一个大于等于T_end的位置，这个位置的索引就是符合条件的数量。
   • 「死亡年份 <= T_start」的人数：用二分找到第一个大于T_start的位置，这个位置的索引就是符合条件的数量。
3. 计算结果：符合要求的人数 = 出生年份 < T_end 的人数 - 死亡年份 <= T_start 的人数。

示例验证 #

• 时间段 1900-1980：
  出生<1980的人数=4，死亡<=1900的人数=0 → 4-0=4，正确。
• 时间段 1980-2023：
  出生<2023的人数=4，死亡<=1980的人数=3（1950、1950、1970都<=1980） →4-3=1，正确。

代码示例（Python） #

import bisect

# 你的示例数据
people = [
    (1920, 1950),  # Paul
    (1930, 1950),  # Sara
    (1960, 2020),  # Mark
    (1960, 1970)   # Lennard
]
births = sorted(b for b, d in people)
deaths = sorted(d for b, d in people)

# 预定义时间段
time_periods = [(1900, 1980), (1980, 2023)]

for start, end in time_periods:
    # 统计出生年份 < end 的人数
    cnt_birth = bisect.bisect_left(births, end)
    # 统计死亡年份 <= start 的人数
    cnt_death = bisect.bisect_right(deaths, start)
    # 计算符合条件的人数
    count = cnt_birth - cnt_death
    print(f"时间段{start}-{end}：{count}人")

方法二：扫描线算法（适合频繁查询任意时段的场景） #

如果之后需要频繁查询不同的时间段，可以用扫描线算法预处理事件点，再通过前缀和快速计算：

1. 把每个人的出生记为 (年份, +1)（新增在世人数），死亡记为 (年份, -1)（减少在世人数），整理成事件列表。
2. 按年份排序事件列表，注意：同一年份的事件，先处理+1（出生）再处理-1（死亡），避免漏算。
3. 生成前缀和数组：按时间顺序累加事件值，记录每个时间点的在世人数。
4. 查询时，通过前缀和数组快速定位时间段内的人数变化。不过这个方法更适合统计某一时刻的在世人数，或者时间段内的在世人数变化，如果你只是需要统计“曾在世”的人数，方法一更直接。

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