如何优化区间与数值的一对一匹配算法，解决大数据量下超时问题

现有代码问题分析 #

你的现有解法的贪心思路是正确的，但是存在两个性能瓶颈：

• 嵌套循环的时间复杂度为O(n*m)，当n和m达到1e6量级时，遍历操作完全无法承受
• 每次匹配成功后对vector执行erase操作，时间复杂度为O(n)，进一步拉高了整体耗时
  整体实际复杂度是O(n*m + n^2)，这就是大测试用例跑7分钟的根本原因。

优化思路（无需推翻现有方案） #

你的核心贪心策略（大数值优先匹配左端点尽可能大的可容纳区间）是完全正确的，只需要把内层的遍历和删除操作替换为时间复杂度更低的有序容器即可，我们可以用C++的std::multiset来维护当前可用的区间右边界，优化后整体时间复杂度降到O((n+m)log(n+m))，完全可以处理1e6量级的数据。

具体步骤 #

1. 保留你原有的排序规则：
   • 区间按左边界降序排序，左边界相同则按右边界降序排序
   • 待匹配数值按降序排序
2. 用双指针把所有左边界小于等于当前数值的区间的右边界，全部插入到multiset中（因为数值从大到小遍历，这些区间的左边界也一定满足后续更小数值的要求，无需重复判断）
3. 对于当前数值，在multiset中查找第一个大于等于当前数值的右边界：
   • 如果找到，匹配成功，计数加一，同时将这个右边界从multiset中删除
   • 如果没找到，说明当前数值没有可匹配的区间，直接跳过

优化后代码示例 #

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct Bounds {
    int min, max;
    bool operator < (const Bounds& rhs) const
    {
        if (min == rhs.min)
            return max > rhs.max;
        else
            return min > rhs.min;
    }
};

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速cin输入，处理大输入必须加
    
    int n, m, rval = 0;
    cin >> n >> m;
    vector<Bounds> bounds(n);
    vector<int> values(m);

    // 读取输入
    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.begin(), bounds.end());
    sort(values.begin(), values.end(), greater<int>());

    multiset<int> right_bounds;
    int ptr = 0; // 区间遍历指针
    for (int val : values) {
        // 把所有左边界<=当前值的区间的右边界加入集合
        while (ptr < n && bounds[ptr].min <= val) {
            right_bounds.insert(bounds[ptr].max);
            ptr++;
        }
        // 找第一个>=当前值的右边界
        auto it = right_bounds.lower_bound(val);
        if (it != right_bounds.end()) {
            rval++;
            right_bounds.erase(it);
        }
    }

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

内容的提问来源于stack exchange，提问作者jesseb0rn