问题：我们得到一个由2n个整数组成的数组，其中这个整数数组中的每对分别代表恐龙的出生年份和死亡年份。我们要考虑的有效年份范围是 [-100000 到 2005]。例如，如果输入为：
-80000 -79950 20 70 22 60 58 65 1950 2004
这意味着第一只恐龙的出生年份分别为-80000和死亡年份-79950。同样，第二只恐龙的寿命从20岁到70岁，依此类推。
我们想知道有史以来活着的恐龙数量最多。编写一个方法来计算它，给定上面的 2n 个整数数组。
任何人都可以建议找出解决方案的方法吗？
编辑尝试使用此>粗略代码
#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] = %2dn", 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]);
}
但产出并不像预期的那样。请告诉我我错过了什么。
将每个恐龙的出生视为一个开放的括号，将死亡视为一个紧密的括号。然后按日期对括号进行排序 - 这将为您提供每个出生和死亡事件的时间顺序。之后，越过括号序列并计算余额（在"（"上递增，在"）"上递减）。跟踪最大平衡，这将是答案。
更新：
C++中的示例源。
输入：恐龙的数量n，然后是2n个出生和死亡日期。
输出：同时生活的最大恐龙数量
#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;
}
附言我假设如果两只恐龙同时出生和死亡，那么它们就不会生活在一起。如果你想要相反的情况，只需将值更改为born=0，dieed=1。
Largest number of dinosaurs that were ever alive at one time?
这是 java 的示例源代码。
输入：恐龙的数量n，n出生日期和n死亡日期。
产量：有史以来存活的恐龙数量最多
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;
}
}
创建一个名为 DinosaurEvent 的结构，并让它存储一年 - 事件发生的年份和事件类型 - 出生或死亡。实现你自己的比较函数，传递给qsort，根据年份和事件进行第一次排序（考虑到死亡是否发生在出生前或相反，即范围是否包含在两端）迭代给定的数组并将所有事件放在一个向量中。之后对向量进行排序并依次处理事件。同时处理给定年份的所有事件（或仅根据语句处理出生或死亡）并重新计算当前现存恐龙的数量（出生增加一，死亡减少一）。始终存储最大值，这将是您的答案。希望这是有道理的。
很抱歉给出了整个解决方案，我无法找到一种方法来给你一个提示，而没有真正说出所有内容。
这里是 python scrypt
n=5
birthAndDeath = [-80000, -79950, 20, 70, 22, 60, 58, 65, 1950, 2004]
birth = [] #date of birth of dinos
death = [] #date of death of dinos
currentAliveDinos=0
maxDinos=0
dateLastBornForMax=0
b = 0
d = 0
#we populate the both arrays for births and deaths
for i in range(0,2*n,2):
birth.append(birthAndDeath[i])
death.append(birthAndDeath[i+1])
#don't forget to sort arrays particuliary for death
death.sort()
birth.sort()
print birth
print death
while b!=5 and d!=5:#there are still unborn dino
if birth[b] < death[d]: # a dino born
currentAliveDinos = currentAliveDinos + 1
b = b + 1
else: # a dino died
currentAliveDinos = currentAliveDinos - 1
d = d + 1
if maxDinos < currentAliveDinos:
maxDinos = currentAliveDinos
dateLastBornForMax=birth[b-1]
print currentAliveDinos
print "max dinos = ", maxDinos, " and last dino born in ", dateLastBornForMax, " when max achieved"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
unsigned int n;
cin >> n;
vector<pair<int, int> > dinos(2*n); // <date, died/born>
unsigned 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;
}