16.10. Number of survivors

subject ：

Given N The year of birth and the year of death of the individual , The first i The year of birth of the individual is birth[i], The year of death was death[i], Implement a method to calculate the year with the largest number of survivors .

You can assume that everyone was born in 1900 - 2000 year （ contain 1900 and 2000 ） Between . If a person is living at any time of the year , Then he should be included in the statistics of that year . for example , Born in 1908 year 、 Die of 1909 People in should be included in 1908 Years and 1909 Year count .

If the number of survivors is the same in multiple years and all are the maximum , Output the smallest year .

Example ：

Input ：
birth = {1900, 1901, 1950}
death = {1948, 1951, 2000}
Output ： 1901
 

Tips ：

0 < birth.length == death.length <= 10000
birth[i] <= death[i]

Ideas 1：

Maintenance interval , First, save the time points of life and death in order , At the same time, the year and number of life and death are hashed map Save it . Initialize three int,cur Represents the current number ,big Represents the largest number of people so far ,year Record the year . Traverse time point , If there is a birth at the current time , It's in cur add , And with big contrast , If cur Bigger , to update big And year. Then we'll see if there was death, If so, start from cur subtract . because death People existed in those days , Only in the next year “ Die completely ”, So from death Update complete cur Don't talk with big Compare .

Code 1：

class Solution {

public:

    int maxAliveYear(vector<int>& birth, vector<int>& death) {

        unordered_map<int, int> b, d;

        set<int> time;

        for (auto i : birth) {

            time.insert(i);

            b[i]++;

        }

        for (auto i : death) {

            time.insert(i);

            d[i]++;

        }

        int cur = 0, big = 0, ans = birth[0];

        for (auto t : time) {

            if (b.count(t)) {

                cur += b[t];

                if (cur > big) {

                    big = cur;

                    ans = t;

                }

            } 

            if (d.count(t)) {

                cur -= d[t];

            }

        }

        return ans;

    }

};

Ideas 2：

Array difference , The principle is to modify at the current time point when life or death occurs , The prefix sum of each subsequent year is the number of people in that year . The first year is [1900, 2000], Both sides include , therefore index Will arrive 101, That is, the array needs to be initialized 102. then death People don't count in that year , When the deposit reaches the time point, it should be postponed for a year , Remember death + 1 In the year . Finally, traverse to get the prefix and the maximum year .

Code 2：

class Solution {

public:

    int maxAliveYear(vector<int>& birth, vector<int>& death) {

        vector<int> time(102);

        for (int i = 0; i < birth.size(); i++) {

            time[birth[i] - 1900]++;

            time[death[i] - 1900 + 1]--;

        }

        int year = 0, ans = 0, cur = 0;

        for (int i = 0; i < 102; i++) {

            cur += time[i];

            if (cur > ans) {

                ans = cur;

                year = i;

            }

        }

        return year + 1900;

    }

};