CODEWITHSUNDEEP
performanceruntime
Ori
Ori

Reputation: 21

Find max value in an array of ranges

Lets say i have an array of birth and death years of 100 people between the years 1900 - 2000.

ergo:

persons[0][birth] = 1900;

persons[0][death] = 1960;

.

.

.

persons[99][birth] = 1904;

persons[99][death] = 1982;

And i would want to find the year that most people lived in between those ranges.

The obvious way is by going through each person, calculate the years he lived (death - birth), and adding these years to an accumulating array using an inside loop. Runtime for that would be O(n^2).

Is there a more efficient way to do this?

Upvotes: 0

Views: 46

Answers (2)

Antonín Lejsek
Antonín Lejsek

Reputation: 6103

The O notation may be a bit misleading sometimes. You do not have only one variable. Number of people is n. Length of life let be y, the whole interval Y. Precisely evaluated Your solution is not O(n^2), but O(MAX(n*y, Y)). If You say, that Y is 100 and always will be, Your solution is O(n), because y<=Y and they are both eliminated as constants. You do twice as much work with twice as much people, so it really is linear, just the constants are high. Marking it O(n^2) strictly speaking means, that length of life is proportional to number of people, that is probably nonsense. Let say, from now on, that y is equal to Y. Now Your solution simplifies to O(n*y).

You can improve Your algorithm. Store +1 for birth and -1 for death into the accumulating array. Only two values for every person. Now You can go through that array once and get number of people living in every year. The time would be O(MAX(n, y)). It is better than solution of @Aziuth when n*log(n) grows faster than y, but worse otherwise.

Upvotes: 1

Aziuth
Aziuth

Reputation: 3902

Create an array that stores a pair of data ([birth or death], year). Every person will create two sets of such data. This takes O(n).

Sort this array by year. This takes O(nlogn).

Process through that array and keep the current amount of people alive in a variable, decreasing and increasing accordingly. Store the maximal amount to that point. This takes again O(n).

Example: A: born 1904, died 1960. B: born 1930, died 1960. C: born 1940, died 1950.

-> array of deaths and births starts as (birth, 1904), (death, 1960), ...

-> array is sorted: (birth, 1904), (birth, 1930), (birth 1940), (death, 1950), (death, 1960), (death, 1960)

-> processing array: At 1904, one person lives. At 1930, two persons live. At...

Upvotes: 0

Related Questions