Find the year with the most number of people alive in Python
>>> 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]
Another solution I just though of:
- Create 2 tables,
birthdates
anddeathdates
. - Accumulate birth dates and death dates in those tables.
- Browse those tables to accumulate the number of alive people at the time.
Grand total complexity is O(n)
Implementation
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())]
Better
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)]