โปรแกรมหาปีที่ประชากรมากที่สุดด้วย Python

สมมติว่าเรามีตาราง 2 คอลัมน์ (birth, death) แต่ละแถวแทนปีเกิดและปีตายของคนคนที่ i ประชากรของปี y คือจำนวนคนที่มีชีวิตอยู่ในปี y คนที่ i นับในปี y เมื่อ y อยู่ในช่วง [birth_i, death_i - 1] (ไม่นับในปีที่ตาย) หาปีแรกที่มีประชากรมากที่สุด

เช่น ข้อมูลเข้า:

ผลลัพธ์คือ 1960

ขั้นตอนการแก้ปัญหา

• d = defaultdict(int) นับประชากรแต่ละปี
• res = [2051, 0] (ปี, จำนวนประชากรสูงสุด)
• วนลูปแต่ละ (YOB, YOD) ใน matrix:
  • วนลูป year จาก YOB ถึง YOD-1:
    • d[year] += 1
    • ถ้า d[year] ≥ res[1]:
      • ถ้า d[year] > res[1]: res = [year, d[year]]
      • มิฉะนั้น: res = [min(year, res[0]), res[1]] (เลือกปีที่น้อยกว่า)
• คืน res[0]

ตัวอย่างโค้ด

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

ข้อมูลเข้า

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

ข้อมูลออก

1960