时间戳

首页 > 解决方案 > 如何将边界列表与数字列表一对一匹配

c++ - 如何将边界列表与数字列表一对一匹配

问题描述

任务

我正在解决一个 leetcode 风格的任务。找到可以排序的值的数量（下限 <= 值 <= 上限）。

输入：第一行包含 n 和 m、范围的数量和值的数量。第二行包含 n 个下限。第三行包含 n 个上限。第四行包含 m 个值。（单界是 li 和 ri）

现在找到值的数量，如果我们以最佳方式进行分类，则可以将其分类。（并输出）

注意：每个值只能分配一个界限，一个界限只能分配一个值。

前任。输入：

3 4
1 7 3
4 9 8
5 2 9 2

输出3。

我的解决方案

我有一个边界结构：

struct Bounds {
    int min, max;
    // operator for sorting both primary and secondary keys
    bool operator < (const Bounds& rhs) const
    {
        if ( min == rhs.min )
            return max > rhs.max;
        else
            return min > rhs.min;
    }
};

并解决如下：

int main()
{   
    int n, m, rval = 0;
    cin >> n >> m;
    Bounds newBound = {0, 0};
    vector<Bounds> bounds(n, newBound);
    vector<int> values(m);

    // get input
    for (int i = 0; i < n; i++)
        cin >> bounds[i].min;
    for (int i = 0; i < n; i++)
        cin >> bounds[i].max;
    for (int i = 0; i < m; i++)
        cin >> values[i];

    // sort Bounds in descending order by lower bound as primary and upper bound as secondary
    std::sort(bounds.begin(), bounds.end(), less<Bounds>());
    //sort values in ascending order
    std::sort(values.begin(), values.end(), greater<int>());

    // for every bound 
    for (int j = 0; j < m; j++) {
        int value = values[j];
        for (int i = 0; i < bounds.size(); i++)
        {
            if (bounds[i].min <= value && value <= bounds[i].max) {
                rval++;
                bounds.erase(bounds.begin() + i);
                break;
            }
        }
    }

    cout << rval << "\n";
}

我的问题

这有效，但是：

  1. 我不认为这是最佳解决方案，
  2. 这很慢，因为一个具有 10^6 值的测试用例需要大约 7 分钟才能解决。

我该如何改进它？还是我应该放弃这种方法？

我认为我的解决方案有 0(n^2 + (n log(n)))

或者换个说法：如何删除嵌套的 for 循环？

标签： c++algorithmsortingoptimization

解决方案

推荐阅读