Algorithm to solve find max no at a time

Question

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.

Can anyone suggest the way to find out solution?

Edit tried with this-> rough code

#include<stdio.h>
#include<stdlib.h>
#include <stddef.h>
static void insertion_sort(int *a, const size_t n) {
    size_t i, j;
    int value;
    for (i = 1; i < n; i++) {
        value = a[i];
        for (j = i; j > 0 && value < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = value;
    }
}


int  main(){
    int arr[10]={-80000,-79950,20,70,22,60,58,65,1950,2004};
    int strt[5],end[5];
    int bal[5];
     int i,j,k,l,m,length;
     l=0;
     m=0;
   for (i=0; i<10; i++){
       //printf("i = %2d arr[i] = %2d\n", i, arr[i]);
       if(i%2==0){
       strt[l]=arr[i];
       l++;
       }else{
       end[m]=arr[i];
       m++;
       }
   }
   insertion_sort(strt, sizeof strt / sizeof strt[0]);
   insertion_sort(end, sizeof end / sizeof end[0]);
   k=sizeof(end)/sizeof(int);
   for(j=0;j<5;j++){
       bal[i]=strt[i]-end[k-1];
       k--;

   }
   length=sizeof bal / sizeof bal[0];
   insertion_sort(bal, sizeof bal / sizeof bal[0]);
   printf("answer is = %2d",bal[length-1]);

}

But output is not as expected. Please tell me what I miss.

Answer 1

Consider each dinosaur birth as an open parenthesis and death as a close one. Then sort the parenthesis by date - this will give you chronological order of every event of birth and death. After that pass over the parenthesis sequence and compute the balance (increment on '(' and decrement on ')' ). Track the maximal balance and it will be the answer.

Update:

Sample source in C++.
Input: number of dinosaurs n, then 2n dates of birth and death.
Output: number of maximal quantity of dinos living at the same time

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > dinos(2*n); // <date, died/born>
    int i;
    for( i = 0; i < n; ++i )
    {
        cin >> dinos[ 2 * i ].first >> dinos[ 2 * i + 1 ].first;
        dinos[ 2 * i ].second = 1; // born
        dinos[ 2 * i + 1 ].second = 0; // died
    }
    sort( dinos.begin(), dinos.end()); // sorts by date first
    int ans = 0, balance = 0;
    for( i = 0; i < dinos.size(); ++i )
        if( dinos[ i ].second ) // someone's born
        {
            ++balance;
            ans = max( ans, balance ); // check for max
        }
        else
            --balance;
    cout << ans << endl;
    return 0;
}

P.S. I assumed that if two dinos born and died at the same time then they didn't live together. If you want the opposite, just change the values as born=0, died=1.

Answer 2

Largest number of dinosaurs that were ever alive at one time?

This is sample source code for java.

Input: number of dinosaurs n, n dates of birth and n dates of death.

Output: largest number of dinosaurs that were ever alive at one time

import java.util.Arrays;

public class Dinosaur {

   public static void main(String args[]) {
        int birthAndDeath[] = { -80000, -79950, 20, 70, 22, 60, 58, 65, 1950, 2004};
        System.out.print("Maximum number of dinosaurs that were ever alive at one time: " + new Dinosaur().findMaxdinosaur(birthAndDeath));
    }

   /**
    * Find the Maximum number of dinosaurs that were ever alive at one time.
    * @param years
    * @return maximum number of dinosaurs that were ever alive at one time.
    */
   public int findMaxdinosaur (int[] years) {
        /** For birth array */
        int birthArray[] = new int [years.length/2];

        /** For death array */
        int deathArray[] = new int [years.length/2]; 

        int birthCounter = 0, deathCounter = 0;
        int currentAliveDinos = 0;

        /** Maximum number of dinosaurs that were ever alive at one time. */
        int maxDinos = 0; 

        int position = 0;

        /** To get the birth and death values in different array */
        for(int index = 0; index < years.length; index = index + 2) {
            birthArray[position] = years[index];
            deathArray[position] = years[index + 1];
            position++;
        }       

        /** Sort the birth and death array in ascending order. */
        Arrays.sort(birthArray);
        Arrays.sort(deathArray);

        /** Calculating max number of dinosaurs that were ever alive at one time **/
        while( birthCounter != years.length/2 && deathCounter != years.length/2) {
            if(birthArray[birthCounter] < deathArray[deathCounter]) {
                currentAliveDinos++;
                birthCounter++;
            } else {
                currentAliveDinos--;
                deathCounter++;
            }
            if(maxDinos < currentAliveDinos) {
                maxDinos = currentAliveDinos;
            }
        }
        return maxDinos;
   }
}