Problem
Given life time of different animals. Find period when maximum number of animals lived.
ex [5, 11], [6, 18], [2, 5],[3,12] etc. year in which max no animals exists.
Solution
#include <iostream>
#include <iomanip>
#include <iterator>
using namespace std;
typedef struct{
int birthYear;
int deathYear;
}LIFE;
typedef struct{
int startYear;
int endYear;
}PERIOD;
int FindMinStartYear(LIFE* anmimals, int len)
{
int startYear = anmimals[0].birthYear;
for(int i = 1; i < len; ++i){
if(anmimals[i].birthYear < startYear){
startYear = anmimals[i].birthYear;
}
}
return startYear;
}
int FindMaxEndYear(LIFE* anmimals, int len)
{
int endYear = anmimals[0].deathYear;
for(int i = 1; i < len; ++i){
if(anmimals[i].deathYear > endYear){
endYear = anmimals[i].deathYear;
}
}
return endYear;
}
int FindPeriodOfMaxAnimal(LIFE* anmimals, int len, PERIOD& p)
{
int startYear = FindMinStartYear( anmimals, len);
int endYear = FindMaxEndYear( anmimals, len);
int* period = new int[endYear - startYear + 1];
for(int i = 0; i < endYear - startYear + 1; ++i){
period[i] = 0;
}
for(int i = 0; i < len; ++i){
for(int j = anmimals[i].birthYear; j <= anmimals[i].deathYear; ++j){
period[j - startYear]++;
}
}
cout << endl;
copy(period, period + endYear - startYear + 1, ostream_iterator<int>(cout, " "));
cout << endl;
int maxAnimals = period[0];
int maxStart = 0;
int maxEnd = 0;
for(int i = 0; i <= endYear - startYear; ++i){
if(period[i] > maxAnimals){
maxStart = i;
maxAnimals = period[i];
}
if(period[i] == maxAnimals){
maxEnd = i;
}
}
delete[] period;
p.startYear = maxStart + startYear;
p.endYear = maxEnd + startYear;
return maxAnimals;
}
int main(int argc, char* argv[])
{
LIFE testCases[] = {
{5, 11},
{6, 18},
{2, 5},
{3, 12}
};
PERIOD p;
int maxAnimals = FindPeriodOfMaxAnimal(testCases, sizeof(testCases)/sizeof(testCases[0]), p);
cout << "In the period " << p.startYear << " and ";
cout << p.endYear << ", there are " << maxAnimals << endl;
return 0;
}
Output
1 2 2 3 3 3 3 3 3 3 2 1 1 1 1 1 1
In the period 5 and 11, there are 3
Press any key to continue . . .