Problem Description
You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i-th person. The population of some year x is the number of people alive during that year. The i-th person is counted in year x's population if x is in the inclusive range [birth_i, death_i - 1]. Note that the person is not counted in the year that they die. Return the earliest year with the maximum population.
Key Insights
- Each person's lifespan can be defined by their birth and death years.
- A year is counted in the population if it falls between the birth year and one year before the death year.
- The problem can be solved using a counting approach where we track population changes over the years based on the birth and death years.
- The maximum population year is the first year with the highest population count during the specified range.
Space and Time Complexity
Time Complexity: O(101) or O(1) since the range of years is fixed (1950 to 2050).
Space Complexity: O(1) as we only need a fixed amount of space to store population counts.
Solution
To solve this problem, we can use an array to count the population changes over the years. We will iterate over the logs and increment the count for the birth year and decrement it for the death year. After processing all logs, we can accumulate the population counts to determine the year with the maximum population. This approach uses an array of size 101 to represent each year from 1950 to 2050.