largest number of dinosaurs that were ever alive at one time

Question: We are given an array of 2n integers wherein each pair in this array of integers represents the year of birth and the year of death of a dinosaurs respectively. The range of valid years we want to consider is [-100000 to 2005]. For example, if the input was:

-80000 -79950 20 70 22 60 58 65 1950 2004

it would mean that the first dinosaur had a birth year of –80000 and an year of death of –79950 respectively. Similarly the second dinosaur lived from 20 to 70 and so on and so forth.

We would like to know the largest number of dinosaurs that were ever alive at one time. Write a method to compute this, given the above array of 2n integers.

Write one of the following methods:

C/C++:
int find_max_dinosaur (int[] years);

Java :
public int findMaxdinosaur (int[] years);

Java answer:

public int findMaxdinosaur( int[] years ) {

    int[] time = new int[ 102006 ];
    int ans = 0; 

    for( int i = 0; i < years.length; i += 2 ) {

        int start = years[ i ];
        int end = years[ i + 1 ];

        for( int j = start; j < end; j++ ) 
            time[ j + 100000 ]++;

     }

     int ans = 0;

     for( int i = 0; i < years.length; i++ ) {

         if( years[ i ] > ans )
             ans = years[ i ];

     }

   return ans;
}

Explanation:

I have a large int array from 0 to 102005 which represents time. When I receive the information from the array about the birth and death years for a dinosaur, I iterate through the array and increment those elements. This is the first for loop.

The second for loop simply iterates through the whole array to find the maximum time.

At first glance, this looks to be between linear and quadratic time, but the constraints are not given so I’m not sure if this is a fast enough solution. If it isn’t, one potential optimization is to keep track of the minimum and maximum elements in years[]. With this, I could just iterate between those two values rather than searching through the whole array to find the maximum. For example, with the sample input, my minimum would be -80000 and my maximum would be 2004 (not because they are the end elements, but because they are the lowest and highest elements in the array), and instead of iterating from 0 to 102005 to find the maximum, I would just need to iterate from 20,000 to 102004. I did not include this, but it can be easily added.

For those of you who do the USACO Training Gateway, this problem is almost completely identical to the 1.2 problem Milking Cows. If you are new to programming, this should be an incentive to do more practice because the chances of you finding a problem you’ve already solved is much greater than if you did not do practice.

And a note to the problem setter: A better idea would be to, instead of using years, use a smaller quantity such as seconds, minutes, or at least days. There is a lot of potential overlap with using a large time quantity such as year. For example, suppose there are two dinosaurs, Dinosaur A and B. Dinosaur A could have a death year of 2000 and Dinosaur B could have a birth year of 2000. However, Dinosaur A could have died in January whereas Dinosaur B could have been born in December. Consequently, they would not be alive at the same time. We are forced to assume that all these dinosaurs have died and were born at the same time on the same day in each year. If you’d like, you may simply state that we could assume the above statement. But without it, there is too much overlap to correctly identify how many dinosaurs were alive at one point in time.