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 <= 1001950 <= birthi < deathi <= 2050
Solution: Simulation
Time complexity: O(n*y)
Space complexity: O(y)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int maximumPopulation(vector<vector<int>>& logs) { vector<int> pop(2051); for (const auto& log : logs) { for (int y = log[0]; y < log[1]; ++y) ++pop[y]; } int ans = -1; int max_pop = 0; for (int y = 1950; y <= 2050; ++y) { if (pop[y] > max_pop) { max_pop = pop[y]; ans = y; } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment