Logic, Loops
You can do this by keeping track of how many people are active for any given year, and then find the start and end of that window:
def most_active(bio_data):
"""Find window of time when most authors were active."""
# START SOLUTION
# Make a minefield of years 1900-1999
century = [0] * 100
# Add 1 in every year when someone was active
for person, start, end in bio_data:
for year in range(start, end + 1):
century[year - 1900] += 1
# Find the period of time when the max number of people were active
best = 0
in_best = True
best_start = 0
best_end = 100
for year, num_active in enumerate(century):
if num_active > best: # New best; start tracking it
best = num_active
in_best = True
best_start = year
elif num_active < best and in_best: # End of best-period window
best_end = year - 1
in_best = False
return best_start + 1900, best_end + 1900
This performs in O(1) time — but it does require sweeping over the lifetime of an author to mark all the years they were active. Can you find a way that reduces the amount of work? It will still be linear time, but will perform better.
You can remove the loop that marks every year an author is active and instead, as you sweep over the century, keep a +/- running count of how many people are active.
def most_active_faster(bio_data):
"""Find window of time when most authors were active."""
# Make two minefields of years 1900-1999
starts = [0] * 100
ends = [0] * 100
for person, start, end in bio_data:
starts[start - 1900] += 1
ends[end - 1900] += 1
best = 0
in_best = False
best_start = 0
best_end = 0
# How many people are currently active/inactive
num_active = 0
for year in range(100):
num_active -= ends[year]
num_active += starts[year]
if num_active > best: # New best; start tracking it
best = num_active
in_best = True
best_start = year
elif in_best and num_active < best: # New best; start tracking it
best_end = year
in_best = False
return best_start + 1900, best_end + 1900