重複しているペアと使用するデータ構造の問題を解決する方法

Question

私たちが持っている交通情報、駅を訪れる列車のような（到着、出発）時間のペアがあります。このT {1,5、2,4、5,9、3,10}のようなもの。次に、このトラフィックを管理するために必要なプラットフォームの最小数を見つける方法。

Answer 1

あなたは最大重複を見つける必要がありますか？これにより、最小限のプラットフォーム数が得られます。 max(times)要素が0に等しい配列を初期化し、各(arrival, departure)区間を繰り返して追加し、その区間にある配列の各要素に1を加えます。

次に、配列の任意の要素の最大値が、必要な最小プラットフォーム数になります。これは整数値の区間で動作します。しかし、配列は最も速い方法ではないかもしれません。私はあなたにそれを残すでしょう。

Answer 2

「このような問題を解決するにはどのようにして、どのデータ構造を処理するのが良いのですか？

あなたは上記の例を挙げました。この種の問題は最適化問題（http://en.wikipedia.org/wiki/Optimization_problem）として知られています。

データ構造の選択は、時間と空間のトレードオフに基づいて行われます。たとえば、単純な配列やハッシュテーブル、あるいはグラフを使って上記の問題を解決することができます。本当に重要なことは、NP-Complete/Hardになるような問題を解決する際に指数関数的な実行時間がかかることがあることです。あなたがn台のプラットフォームとm列車を持っているあなたの例を考えてみると（n & mが非常に大きい場合）、コンビナトリアル爆発の可能性があります。

また指数関数的な時間となり、NP-Complete/Hardの問題がある場合は、ヒューリスティックなアルゴリズムがいくつかあります（例：旅行用セールスマンの問題はAnt Colony Optimizationで解決できます）最も最適なもの。

ここでは、データ構造よりもアルゴリズムが重要です。

Answer 3

このような構造体の配列行います（時間、IsArrival）、IsArrival到着を= +1または-1時間キーによる

ソートそれは（アカウントに等しい時間の場合を取る）出発のための

を

初期PlatformsNeededソートされた配列を介し= 0

ウォーク、PlatformsNeededにIsArrivalを追加し、最大値

Answer 4

を覚えnは所与の時間対の数である時間O中の溶液を（N Nログ）、あります。 あなたは次の質問に答えなければなりません：駅に何台もの列車が同時に立っていますか？ これを行うには、最初に時間値を正規化します。興味深い何かが発生する可能性のある時間セグメントをすべて特定します。これを行うには、すべての到着時間と出発時間を並べ替え、重複を排除します。

あなたの例では、T = {[1,5]、[2,4]、[5,9]、[3,10]}となり、結果は配列[ A 、3,4,5,9,10]およびサイズm = 7である。

ここで、各ペアの到着時間と出発時間を、列車がステーションを占有する時間セグメントに変換する。 e。配列Aの時間値のインデックスを（バイナリ検索を使用して）検索します。 E. [3,10]の場合、0から数えてインデックス2と6が得られます。

これは簡単な部分のためでした。時間値をインデックスでソートして照合すると、それぞれO（n log n）で実行されます。今度は各指標を数えなければなりません。その時点で駅に何台の列車が立っていますか？効率的に行うには、セグメントツリーを使用します。

このサイトでは、セグメントの木を使用する方法について紹介します。以下では http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees

、あなたがC++で実装を見つけることができます。私はあなたのニーズにそれを適応させることを願っています。ご質問が残っている場合は、お気軽にお問い合わせください。

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

/** Given a number n and n pairs of arrival and departure times of trains, 
* this program calculates the number of platforms needed in time O(n log n) 
* If a train arrives exactly when another one leaves the station, you need 
* two platforms. */ 

int main() { 
    int n; 
    cin >> n; 

    vector< pair<int,int> > T(n); 
    vector< int   > A(2*n); 

    for (int i = 0; i < n; ++i) { 
     int arrival, departure; 
     cin >> arrival >> departure; 
     A[2*i] = arrival; 
     A[2*i+1] = departure; 
     T[i] = pair<int,int>(arrival, departure); 
    } 
    sort(A.begin(), A.end()); 
    int m = unique(A.begin(), A.end()) - A.begin(); 

    // for easy indexing, we need m to be a potency of 2 
    int pot2m = 1; while (pot2m < m) pot2m *= 2; 

    // Elements pot2m ... pot2m + m represent the bottom layer of the segment tree 
    vector<int> segtree(2*pot2m+1, 0); 

    // Now let's add everything up 
    for (int i = 0; i < n; ++i) { 
     int arrival = find(A.begin(), A.end(), T[i].first) - A.begin(); 
     int departure = find(A.begin(), A.end(), T[i].second) - A.begin(); 
     // Now increment 
     int a = arrival + pot2m; 
     int b = departure + pot2m + 1; 
     while (a < b) { 
      if (a % 2 == 1) ++segtree[a]; 
      if (b % 2 == 1) ++segtree[b-1]; 
      a = (a+1)/2; 
      b = b/2; 
     } 
    } 

    // Find the maximum value in the cells 
    int a = pot2m; 
    int b = pot2m + m; 
    while (a < b) { 
     int i, j; 
     for (i = a/2, j = a; j < b-1; ++i, j+=2) { 
      segtree[i] += max(segtree[j], segtree[j+1]); 
     } 
     if (j == b-1) segtree[i] += segtree[j]; // To handle odd borders 
     a /= 2; 
     b /= 2; 
    } 
    cout << "You need " << segtree[1] << " platforms." << endl; 

    return 0; 
}