算法来解决发现的最大不同时 [英] Algorithm to solve find max no at a time

问题描述

问：我们给出2n个整数，其中每对整数数组重新诞生的一年的恐龙死亡的分别在今年presents的数组。我们要考虑年份的有效范围为[-100000至2005年。例如，如果输入是：

Question: We are given an array of 2n integers wherein each pair in this array of integers represents the year of birth and the year of death of a dinosaurs respectively. The range of valid years we want to consider is [-100000 to 2005]. For example, if the input was:

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

这将意味着，第一个恐龙具有-80000出生年份和-79950死亡分别为一年。类似地，第二恐龙住从20到70等等，等等。

it would mean that the first dinosaur had a birth year of –80000 and an year of death of –79950 respectively. Similarly the second dinosaur lived from 20 to 70 and so on and so forth.

我们想知道最多的恐龙是有史以来活一次的。写一个方法来计算这一点，给予2n个整数上述阵列。

We would like to know the largest number of dinosaurs that were ever alive at one time. Write a method to compute this, given the above array of 2n integers.

任何人都可以提出来找出解决办法的途径？

Can anyone suggest the way to find out solution?

编辑试图与这 - > 粗略code

Edit tried with this-> rough code

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

}

但产量并不如预期。 请告诉我，我错过了。

But output is not as expected. Please tell me what I miss.

推荐答案

考虑每个恐龙的诞生作为一个开放的括号和死亡紧密之一。然后排序括号按日期 - 这会给你的出生和死亡的每一个事件的时间顺序。即越过括号序列后，并计算余额（增量上（和递减的'）'）。跟踪的最大平衡，这将是答案。

Consider each dinosaur birth as an open parenthesis and death as a close one. Then sort the parenthesis by date - this will give you chronological order of every event of birth and death. After that pass over the parenthesis sequence and compute the balance (increment on '(' and decrement on ')' ). Track the maximal balance and it will be the answer.

更新：

示例源在C ++中。
输入：恐龙数量的 N 的，生和死的那么的 2N 的日期。
输出：生活在同一时间恐龙的最大数量数

Sample source in C++.
Input: number of dinosaurs n, then 2n dates of birth and death.
Output: number of maximal quantity of dinos living at the same time

#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 我以为，如果两个恐龙诞生，并在同一时间死了，然后他们并没有住在一起。如果你想的相反，因为天生= 0只是改变了值，死亡= 1。

P.S. I assumed that if two dinos born and died at the same time then they didn't live together. If you want the opposite, just change the values as born=0, died=1.

这篇关于算法来解决发现的最大不同时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！