Q:

largest number of dinosaurs that were ever alive

Possible Duplicate:
algorthim to solve find max no at a time 

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.
Here's what I've tried so far:
#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]);
}

A:

I would do something like:

create a map to hold the data
read in a pair
For i = pair.first to pair.second ++map[i]
if there are more pairs, repeat from 2
Find the element in the map with the largest count. The key for that element is the year.

In theory, you could use a vector instead of a map, but it's probably going to be sparsely enough populated that a map makes more sense.

