算法一次解決max max問題

Question

問題：我們給出了一個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

把每個恐龍的出生看作是一個開放的括號和死亡的關係。然後按照日期對括號進行排序 - 這會給你每個出生和死亡事件的時間順序。之後，通過括號序列並計算餘額（'（'上的遞增和'）'上的遞減）。跟蹤最大的平衡，這將是答案。

更新：在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; 
} 

P.S.恐龍的最大數量的我假設如果兩個恐龍同時出生並死亡，那麼他們並不住在一起。如果你想得到相反的結果，只需將值改爲出生= 0，死亡= 1。

Answer 2

創建一個名爲DinosaurEvent的結構，讓它存儲一年 - 事件發生的年份和事件類型 - 出生或死亡。實現你自己的比較函數來傳遞給qsort，首先根據年份進行排序，然後再根據事件進行排序（如果死亡發生在出生前或其他方式（即任一端的範圍包含在內），請對其進行排序）對給定的數組進行迭代並將所有事件放入向量中。之後依次對矢量和流程事件進行排序。同時處理某一年某一年的所有事件（或者根據聲明僅處死或死亡），並重新計算當前活恐龍的數量（因爲死亡減少一個而增加一個）。隨時存儲最大值，這將是您的答案。希望這是有道理的。

對不起，我提供的整個解決方案無法找到一種方法給你一個提示，而沒有實際說出這一切。

Answer 3

這裏，蟒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" 

Answer 4

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

Answer 5

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