c++ - 存活的恐龙数量最多

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




我们给定了一个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] = %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]);
}

最佳答案

我会做类似的事情：


创建一个地图来保存数据
一对读
对于i = pair.first至pair.second ++ map [i]
如果有更多对，则从2开始重复
在地图上找到计数最大的元素。该元素的关键是年份。


从理论上讲，您可以使用向量代替地图，但是由于人口稀少，地图可能更有意义。

关于c++ - 存活的恐龙数量最多，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14658500/