最大的恐龍數量是有史以來活着

Question

可能重複：
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]); 
} 

Answer 1

我會做這樣的事情：

1. 創建了一個map來
2. 讀一對
3. 對於數據i = pair.first to pair.second ++ map [i]
4. 如果有更多對，則重複2
5. 在地圖上查找具有最大計數的元素。這一元素的關鍵是今年。

從理論上講，您可以使用矢量而不是地圖，但它可能會填充足夠稀疏，地圖更有意義。