Living People

16.10 Living People: Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive. You may assume that all people were born between 1900 and 2000 (inclusive). If a person was alive during any portion of that year, they should be included in that year's count. For example, Person (birth = 1908, death = 1909) is included in the counts for both 1908 and 1909.

• Brute force: Go through each year, and increment a count to see how many people are alive in said year. To do this, we have have a vector<pair<int>> that maps year:count. Iterate through the original list starting with the first year, and iterate through the remainder of the list by simply checking if said year is within the boundary of the current year. This will take a nest for loop, O(n^2).

• Optimized:

  • If we sort both the deaths and years we can create the following visualization.

    • Green represents the amount of births accumulated over a period of time. And red represents the accumulation of deaths of time. The difference of births and deaths (outlined in blue) indicates to us the amount of people who are alive of said current year.

  • So algorithm now:

    • Sort births and deaths.

    • Fill in the gaps between the years (optional). When we have one birth, this means +1 accumulation on births. If nothing happens is said year, then the accumulation stays the same.

int mostAlive(vector<int> &births, vector<int> & deaths) {
    sort(births.begin(), births.end());
    sort(deaths.begin(), deaths.end());

    //for (auto i : births) cout << i << " "; cout << "\n";
    //for (auto i : deaths) cout << i << " "; cout << "\n";

    int current_max_year = 0;
    int current_alive = 0;
    int current_max = 0;

    // index iterators
    int birth_itr = 0, death_itr = 0;
    while (birth_itr < births.size() && death_itr < deaths.size()) {
        // if the current birth year is smaller than the current death year
        // we increment birth_itr, as it will be larger next
        // in addition, current alive increases.
        if (births[birth_itr] < deaths[death_itr]) {
            // maintain the current max
            current_alive++;
            // if the number of people currently alive exceeds
            // the number of people we've maintained as max live,
            // then we update the max alive, as well as the year
            if (current_alive > current_max) {
                current_max = current_alive;
                current_max_year = births[birth_itr];
            }

            birth_itr++;
        }
        else {
            current_alive--;
            death_itr++;
        }
    }

    return current_max_year;
}

int main()
{
    // assuming this is how the data will be represented
    vector<int> births = 
    {
        1900, 1902, 1907, 1910,
        1915, 1917, 1950, 1977,
        1980, 1985, 1989, 1994
    };

    vector<int> deaths =
    {
        1944, 1955, 1959, 1960,
        1966, 1977, 1988, 1989,
        1990, 1991, 1993, 1999
    };

    cout << mostAlive(births, deaths) << endl;

    births = {
        12, 20, 10, 01, 10, 23, 13, 90, 83, 75
    };

    deaths = {
        15, 90, 98, 72, 98, 82, 98, 98, 99, 94
    };

    cout << mostAlive(births, deaths) << endl;
    pause();
}