Chương trình tìm năm có dân số lớn nhất bằng Python

Cho bảng hai cột (birth, death) biểu thị năm sinh và năm chết của mỗi người. Dân số năm y là số người còn sống trong năm y (tức y ∈ [birth_i, death_i - 1]). Tìm năm sớm nhất có dân số lớn nhất.

Ví dụ: [[1970,2010],[1960,2020],[1940,1970]] → năm 1960 có dân số 2 (người sinh 1960 và 1940), là năm sớm nhất đạt max.

Thuật toán giải quyết

• Dùng defaultdict(int) d để đếm dân số mỗi năm.
• res := [2051, 0] (năm, dân số max).
• Với mỗi (YOB, YOD):
  • Với year từ YOB đến YOD-1: d[year]++.
  • Nếu d[year] ≥ res[1]:
    • Nếu >: res = [year, d[year]].
    • Nếu =: res = [min(year, res[0]), res[1]] (giữ năm sớm hơn).
• Trả về res[0].

Ví dụ triển khai

from collections import defaultdict

def solve(matrix):
    d = defaultdict(int)
    res = [2051, 0]
    for YOB, YOD in matrix:
        for year in range(YOB, YOD):
            d[year] += 1
            if d[year] >= res[1]:
                if d[year] > res[1]:
                    res = [year, d[year]]
                else:
                    res = [min(year, res[0]), res[1]]
    return res[0]

matrix = [[1970,2010],[1960,2020],[1940,1970]]
print(solve(matrix))

Đầu vào

[[1970,2010],[1960,2020],[1940,1970]]

Đầu ra

1960