解决一次查找最大值的算法

Question

问题:我们得到一组2n个整数,其中这个整数数组中的每一对分别代表恐龙的出生年份和死亡年份.我们要考虑的有效年份范围是[-100000到2005].例如,如果输入是:

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

这意味着第一只恐龙的出生年份为-80000,死亡年份为-79950.同样,第二只恐龙的寿命为20至70岁,依此类推.

我们想知道有史以来最多的恐龙活着.在给定上述2n个整数数组的情况下,编写一个计算方法.

谁能建议找出解决方案的方法？

编辑尝试使用this->粗略代码

#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]);

}

但产出不如预期.请告诉我我错过了什么.

Answer 1

将每个恐龙的出生视为一个开放的括号,将死亡视为一个接近的恐龙.然后按日期对括号进行排序 - 这将为您提供每个出生和死亡事件的时间顺序.之后,通过括号序列并计算余额(增加'('和减​​少')').跟踪最大平衡,这将是答案.

更新:

C++中的示例源代码.
输入:恐龙数n,然后是出生和死亡的2n个日期.
输出:同时生活的最大dinos数量

#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;
}

PS我认为,如果两个dinos同时出生并死亡,那么他们就不会生活在一起.如果你想要相反,只需将值更改为born = 0,died = 1.