c++ - 如何更快地比较结构(谁遇到最多人的问题)

Question

首先我会说我不是母语人士，所以请原谅我的语法错误。

我是一名大学生，我的任务如下:我有一个输入，告诉我人数，然后每一行包含到达时间和离开时间，两个自然数用空格分隔.

我必须找到与最多人会面的人(的索引)，然后输出该人的会面次数。

示例输入和输出:

如果 A 的日期戳为 3 和 6，而 B 的日期戳为 6 和 7，则仍视为 session 。

我已经使用固定大小的结构数组解决了这个问题，该数组将每个人与其他人进行比较以找出 session 次数，然后搜索 session 次数最多的人。

我的问题是这段代码非常慢，我必须处理最多包含 200000 人和 1 到 1000000 范围内的时间戳的输入。

这个 - 将每个人与其他人进行比较 - 解决方案适用于小样本量，但它不可能适用于 200000 个结构。此外，此代码必须在 0.2 秒内成功运行。

有什么方法可以更快地解决这个问题？

#include <iostream>

using namespace std;

const int maxN = 20000;

struct Data {
    int arrival;
    int departure;
    int meetings = -1;
};

int main()
{
    Data x[maxN];
    int N;

    ///input
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x[i].arrival;
        cin >> x[i].departure;
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++){
            if ( ((x[i].arrival >= x[j].arrival && x[i].arrival <= x[j].departure) || (x[i].departure >= x[j].arrival && x[i].departure <= x[j].departure)) ||  ((x[j].arrival >= x[i].arrival && x[j].arrival <= x[i].departure) || (x[j].departure >= x[i].arrival && x[j].departure <= x[i].departure)) ) {
                x[i].meetings++;

            }
        }
    }

    int maxInd = 0;
    int maximum = 0;
    for(int i = 0; i < N; i++) {
        if (x[i].meetings > maximum){
            maxInd = i;
            maximum = x[i].meetings;
        }
    }

    ///output
    cout << maxInd+1 << endl;
    cout << maximum << endl;

    return 0;
}

Answer 1

我只会给你一个起点...

如果我必须解决它，我将从定义以下结构开始:

 struct come_or_go {
      size_t person_index;
      int time;
      bool arrival; // true for arrival, false for leaving
 };

接下来我会将输入读入 vector<come_or_go>每个人有两个条目。到达时一个，离开时一个。接下来，我将根据元素 time 对该 vector 进行排序成员。最后我想出了一个聪明的主意，只需要遍历这个 vector 一次。

到目前为止，我能提供的就是这些，也许我会在可以提供更多提示时更新。希望这有助于将您推向不同的方向，因为您的蛮力只会因复杂性而失去作用。与其试图“更快”地获取细节，不如改变整体方法。