{"id":8444,"date":"2021-05-08T23:24:28","date_gmt":"2021-05-09T06:24:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8444"},"modified":"2021-05-08T23:43:18","modified_gmt":"2021-05-09T06:43:18","slug":"leetcode-1854-maximum-population-year","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1854-maximum-population-year\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1854. Maximum Population Year"},"content":{"rendered":"\n

You are given a 2D integer array logs<\/code> where each logs[i] = [birthi<\/sub>, deathi<\/sub>]<\/code> indicates the birth and death years of the ith<\/sup><\/code> person.<\/p>\n\n\n\n

The population<\/strong> of some year x<\/code> is the number of people alive during that year. The ith<\/sup><\/code> person is counted in year x<\/code>‘s population if x<\/code> is in the inclusive<\/strong> range [birthi<\/sub>, deathi<\/sub> - 1]<\/code>. Note that the person is not<\/strong> counted in the year that they die.<\/p>\n\n\n\n

Return the earliest<\/strong> year with the maximum population<\/strong><\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> logs = [[1993,1999],[2000,2010]]\nOutput:<\/strong> 1993\nExplanation:<\/strong> The maximum population is 1, and 1993 is the earliest year with this population.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> logs = [[1950,1961],[1960,1971],[1970,1981]]\nOutput:<\/strong> 1960\nExplanation:<\/strong> \nThe maximum population is 2, and it had happened in years 1960 and 1970.\nThe earlier year between them is 1960.<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= logs.length <= 100<\/code><\/li>
  • 1950 <= birthi<\/sub> < deathi<\/sub> <= 2050<\/code><\/li><\/ul>\n\n\n\n
    Solution: Simulation<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n*y)
    Space complexity: O(y)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumPopulation(vector>& logs) {\n    vector pop(2051);\n    for (const auto& log : logs) {\n      for (int y = log[0]; y < log[1]; ++y)\n        ++pop[y];\n    }\n    int ans = -1;\n    int max_pop = 0;\n    for (int y = 1950; y <= 2050; ++y) {\n      if (pop[y] > max_pop) {\n        max_pop = pop[y];\n        ans = y;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[222,179],"class_list":["post-8444","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-easy","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8444","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8444"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8444\/revisions"}],"predecessor-version":[{"id":8446,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8444\/revisions\/8446"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8444"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8444"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8444"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}