找到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.两者 - readability和efficiency计数.此外,由于某些原因,我的代码将不会打印[1938, 1939].

更新

输入是一个list元组,其中元组的第一个元素是year人出生时的元素,而第二个元素tuple是死亡年份.

更新2

结束一年(元组的第二部分)和一个人活着的一年(所以如果这个人死了Sept 1939(我们不关心这个月),他实际上是在1939年活着,至少是其中的一部分) .这应该可以解决1939年的结果缺失问题.

最佳方案？

虽然可读性有利于@joran-beasley,但对于更大的输入,最有效的算法由@ njzk2提供.感谢@ hannes-ovrén 在Gist上为IPython笔记本提供分析

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)]

Answer 2

>>> from collections import Counter
>>> from itertools import chain
>>> def most_pop(pop):
...     pop_flat = chain.from_iterable(range(i,j+1) for i,j in pop)
...     return Counter(pop_flat).most_common()
...
>>> most_pop([(1920, 1939), (1911, 1944), (1920, 1955), (1938, 1939)])[0]