如何解决涉及重叠对和使用哪种数据结构的问题

Question

有一个火车站，我们有它的交通信息，它像(到达，出发)时间对访问该站的列车。像这样的T{ 1,5,2,4,5,9,3,10 }。然后如何找到管理此流量所需的最小平台数量。

Answer 1

你需要找出最大的重叠，对吧？这将为您提供最小数量的平台。只需用等于0的max(times)元素初始化一个数组，然后在每个(arrival, departure)间隔中添加然后迭代，将间隔中的每个数组元素加1即可。

那么数组中任意元素的最大值就是所需的最小平台数。这适用于整数值间隔。不过，数组可能不是最快的方法。我把这事留给你了。

Answer 2

在O( given )时间内有一个解，其中n是给定的时间对的数量。你必须回答这个问题:同时有多少列火车停在车站？要做到这一点，我们首先对时间值进行“标准化”：确定所有可能发生有趣事情的时间段。为此，请对给定的所有到达和离开时间进行排序，并消除重复。

在T= {1,5，2,4，5,9，3,10}的示例中，这将产生一个时间点为1,2,3,4,5,9,10，大小为7的数组A。

现在我们将每对列车的到达和出发时间转换为列车占用车站的时间段，即我们在数组A中找到时间值的索引(通过二进制搜索)。例如，对于3，10，我们得到索引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;
}

Answer 3

我将使用您的主题行问题“如何解决这类问题，哪种数据结构更适合处理？”

您已经为上述内容提供了一个示例。这类问题被称为优化问题(http://en.wikipedia.org/wiki/Optimization_problem)。

数据结构的选择将基于空间/时间的权衡。例如，人们可以通过使用简单的数组或哈希表或图形来解决上述问题。真正重要的是，有时在解决这些问题时可能会花费指数级的运行时间，这可能会使它们成为NP-Complete/Hard。假设您有n个站台和m个列车(其中n&m非常大)，则存在组合爆炸的可能性。

此外，如果它的结果是指数时间，并且是NP完全/困难问题，那么也有几种启发式算法(例如，可以使用蚁群优化解决旅行商问题)来解决它，可能不是最优的算法。

在这种情况下，算法比数据结构更重要。