python - 用 Python 找出在世人数最多的年份

Question

给定一个包含出生年份和结束年份(都在 1900 和 2000 之间)的人的列表，找出在世人数最多的年份。

这是我的蛮力解决方案:

def most_populated(population, single=True):
    years = dict()
    for person in population:
        for year in xrange(person[0], person[1]):
            if year in years:
                years[year] += 1
            else:
                years[year] = 0
    return max(years, key=years.get) if single else \
           [key for key, val in years.iteritems() if val == max(years.values())]

print most_populated([(1920, 1939), (1911, 1944),
                      (1920, 1955), (1938, 1939)])
print most_populated([(1920, 1939), (1911, 1944),
                      (1920, 1955), (1938, 1939), (1937, 1940)], False)

我正试图在 Python 中找到一种更有效的方法来解决这个问题。 可读性 和效率 都很重要。此外，出于某种原因，我的代码不会打印 [1938, 1939] 而它应该。

更新

输入是元组的列表，其中元组的第一个元素是人出生的年，元组的第二个元素 是死亡年份。

更新 2

结束年份(元组的第 2 部分)和此人在世的年份一样重要(所以如果此人在 1939 年 9 月 去世(我们不关心月份)，他实际上在 1939 年还活着，至少是其中的一部分)。这应该可以修复结果中缺失的 1939'。

最佳解决方案？

虽然可读性有利于 @joran-beasley ，对于更大的输入，最有效的算法由 @njzk2 提供.感谢@hannes-ovrén 在 IPython notebook on Gist 中提供分析

Answer 1

我想到的另一个解决方案:

• 创建 2 个表，birthdates 和 deathdates。
• 在这些表中累积出生日期和死亡日期。
• 浏览这些表格以累积当时活着的人数。

总复杂度为 O(n)

实现

from collections import Counter

def most_populated(population, single=True):
    birth = map(lambda x: x[0], population)
    death = map(lambda x: x[1] + 1, population)
    b = Counter(birth)
    d = Counter(death)
    alive = 0
    years = {}
    for year in range(min(birth), max(death) + 1):
        alive = alive + b[year] - d[year]
        years[year] = alive
    return max(years, key=years.get) if single else \
           [key for key, val in years.iteritems() if val == max(years.values())]

更好

from collections import Counter
from itertools import accumulate
import operator

def most_populated(population, single=True):
    delta = Counter(x[0] for x in population)
    delta.subtract(Counter(x[1]+1 for x in population))
    start, end = min(delta.keys()), max(delta.keys())
    years = list(accumulate(delta[year] for year in range(start, end)))
    return max(enumerate(years), key=operator.itemgetter(1))[0] + start if single else \
           [i + start for i, val in enumerate(years) if val == max(years)]