- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a table with two columns (birth, death) where each row is representing the birth and death years of the ith person. The population of some year y is the number of people alive during y. The ith person is counted in year y's population when y is in the inclusive range [birth_i, death_i - 1]. (The person is not counted in the year that they die). So, we have to find the earliest year with the maximum population.

So, if the input is like

Birth | Death |

1970 | 2010 |

1960 | 2020 |

1940 | 1970 |

then the output will be 2 because there is only one value that matches with target, that is nums[4], so i = 4. Now |4-2| = 2.

To solve this, we will follow these steps −

d := A map, where if some key is not found, return 0

res := a list with two items [2051, 0]

for each year of birth YOB, and year of death YOD in matrix, do

for year in range YOB to YOD, do

d[year] := d[year] + 1

if d[year] >= res[1], then

if d[year] > res[1], then

res := a list with two elements [year, d[year]]

otherwise,

res := a list with two elements [(minimum of year and res[0]), res[1]]

return res[0]

Let us see the following implementation to get better understanding −

from collections import defaultdict def solve(matrix): d = defaultdict(int) res = [2051, 0] for YOB, YOD in matrix: for year in range(YOB, YOD): d[year] += 1 if d[year] >= res[1]: if d[year] > res[1]: res = [year, d[year]] else: res = [min(year, res[0]), res[1]] return res[0] matrix = [[1970,2010],[1960,2020],[1940,1970]] print(solve(matrix))

[[1970,2010],[1960,2020],[1940,1970]]

1960

- Related Questions & Answers
- Program to find maximum possible population of all the cities in python
- Program to find maximum ascending subarray sum using Python
- Program to find path with maximum probability using Python
- Program to find maximum width ramp in Python
- Program to find maximum erasure value in Python
- Program to find maximum building height in Python
- Program to find maximum equal frequency in Python
- Program to find maximum number of balls in a box using Python
- Program to find maximum number of coins we can get using Python
- Python program to find the maximum of three numbers
- Program to find maximum in generated array in Python
- Program to find maximum average pass ratio in Python
- Program to find maximum ice cream bars in Python
- Program to find maximum subarray min-product in Python
- How to find the first date of a given year using Python?

Advertisements