Maximum Population Year

🏠 ⬅️ ➡️

You are given a 2D integer array logs where each logs[i] = [birthi, deathi] indicates the birth and death years of the ith person.

The population of some year x is the number of people alive during that year. The ith person is counted in year x's population if x is in the inclusive range [birthi, deathi - 1]. Note that the person is not counted in the year that they die.

Return the earliest year with the maximum population.

Example 1:

Input: logs = [[1993,1999],[2000,2010]] Output: 1993 Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2:

Input: logs = [[1950,1961],[1960,1971],[1970,1981]] Output: 1960 Explanation: The maximum population is 2, and it had happened in years 1960 and 1970. The earlier year between them is 1960.

Constraints:

  • 1 <= logs.length <= 100
  • 1950 <= birthi < deathi <= 2050
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: dp = selected_real_kind(15)

    integer, dimension(:), allocatable :: logs
    integer :: n, i, j, k, m, max_pop, min_year, max_year, pop
    logical :: found

    ! read input
    read(*,*) n
    allocate(logs(n))
    do i = 1, n
        read(*,*) logs(i)%birth, logs(i)%death
    end do

    ! sort by birth year
    call sort(logs)

    ! find earliest year with maximum population
    max_pop = 0
    min_year = huge(min_year)
    max_year = -huge(max_year)
    do i = 1, n
        pop = 0
        found = .false.
        do j = 1, n
            if (logs(j)%birth >= logs(i)%birth .and. &
                logs(j)%death <= logs(i)%death) then
                pop = pop + 1
                found = .true.
            end if
        end do
        if (found) then
            if (pop > max_pop) then
                max_pop = pop
                min_year = logs(i)%birth
                max_year = logs(i)%death
            else if (pop == max_pop) then
                if (logs(i)%birth < min_year) then
                    min_year = logs(i)%birth
                end if
                if (logs(i)%death > max_year) then
                    max_year = logs(i)%death
                end if
            end if
        end if
    end do

    write(*,'(I0)') min_year

contains

    subroutine sort(arr)
        implicit none
        integer, dimension(:), intent(inout) :: arr
        integer :: i, j, temp

        do i = 1, size(arr)-1
            do j = i+1, size(arr)
                if (arr(i)%birth > arr(j)%birth) then
                    temp = arr(i)%birth
                    arr(i)%birth = arr(j)%birth
                    arr(j)%birth = temp
                    temp = arr(i)%death
                    arr(i)%death = arr(j)%death
                    arr(j)%death = temp
                end if
            end do
        end do
    end subroutine sort

end program main
❌ Compiled
❌ Executed
❌ Correct 
module PopulationCounter
contains
    function get_earliest_year_with_max_population(logs) result(earliest_year)
        integer, intent(in) :: logs(:, :)
        integer :: birth(size(logs, 1)), death(size(logs, 1)), population(0:2050)
        integer :: i, j, max_population, earliest_year

        ! Initialize the birth and death years
        do i = 1, size(logs, 1)
            birth(i) = logs(i, 1)
            death(i) = logs(i, 2)
        end do

        ! Initialize the population array
        population = 0

        ! Loop through each year and increment the population
        do i = 1950, 2050
            do j = 1, size(logs, 1)
                if (i >= birth(j) .and. i <= death(j)) then
                    population(i) = population(i) + 1
                end if
            end do
        end do

        ! Find the earliest year with the maximum population
        max_population = maxval(population)
        earliest_year = minval(pack((/ (i, i = 1950, 2050) /), population == max_population))
    end function get_earliest_year_with_max_population
end module PopulationCounter

! Test the function with the given examples
program test_population_counter
    use PopulationCounter
    implicit none
    integer, parameter :: logs(2, 2) = reshape([1993, 1999, 2000, 2010], shape(logs))
    integer, parameter :: expected_earliest_year = 1993
    integer :: earliest_year

    earliest_year = get_earliest_year_with_max_population(logs)

    if (earliest_year == expected_earliest_year) then
        print *, "Test 1: Passed"
    else
        print *, "Test 1: Failed"
    end if

    integer, parameter :: logs2(3, 2) = reshape([1950, 1961, 1960, 1971, 1970, 1981], shape(logs2))
    integer, parameter :: expected_earliest_year2 = 1960
    earliest_year = get_earliest_year_with_max_population(logs2)

    if (earliest_year == expected_earliest_year2) then
        print *, "Test 2: Passed"
    else
        print *, "Test 2: Failed"
    end if
end program test_population_counter
🌐 Data from online sources 
def maxAliveYear(logs):
    years = [0] * 101
    for log in logs:
        years[log[0] - 1950] += 1
        years[log[1] - 1950] -= 1
    max_population = years[0]
    max_year = 1950
    for i in range(1, 101):
        years[i] += years[i - 1]
        if years[i] > max_population:
            max_population = years[i]
            max_year = i + 1950
    return max_year

The algorithm iterates through the logs and increments the birth year and decrements the death year in the years array. Then, starting from the first year, it accumulates the population for each year by summing up the previous year's population with the current year's population. After that, it checks which year has the maximum population and returns that year.

🌐 Data from online sources 
int maxAliveYear(vector<vector<int>>& logs) {
    vector<int> years(101, 0);
    for (vector<int> log : logs) {
        years[log[0] - 1950]++;
        years[log[1] - 1950]--;
    }
    int max_population = years[0];
    int max_year = 1950;
    for (int i = 1; i < 101; i++) {
        years[i] += years[i - 1];
        if (years[i] > max_population) {
            max_population = years[i];
            max_year = i + 1950;
        }
    }
    return max_year;
}

The algorithm iterates through the logs and increments the birth year and decrements the death year in the years array. Then, starting from the first year, it accumulates the population for each year by summing up the previous year's population with the current year's population. After that, it checks which year has the maximum population and returns that year.