活动选择问题C++代码触发TLE(Time Limit Error)问题排查

问题背景 #

求解活动选择（最大会议数安排）问题时，代码提交后触发时间超限（Time Limit Error, TLE），需要定位代码性能缺陷。
题目规则如下：

• 给定N场会议的开始时间数组Start与结束时间数组End，仅有1间会议室可用
• 需返回可安排的会议编号，要求最终可组织的会议总数最大
• 约束条件：选中会议的开始时间不能与任意已选会议的结束时间相等；若多个会议结束时间相同，优先选择编号更小的会议

原始问题代码 #

#include<algorithm>
vector<int> maximumMeetings(vector<int> &start, vector<int> &end) {
    vector<vector<int>> A;
    vector<int> temp ;
    for(int i=0; i<start.size(); i++){
        temp.clear();
        temp.push_back(start[i]);
        temp.push_back(end[i]);
        temp.push_back(i+1);
        A.push_back(temp);
    }
    sort(A.begin(),A.end(),[](vector<int>A,vector<int>B){
        if(A[1]!=B[1]){
            return A[1]<B[1];
        }
        else{
            return A[2]<B[2];
        }
        
    });
    vector<int> ans;
    ans.push_back(A[0][2]);
    int j=0;
    for(int i=1; i<A.size(); i++){
        if(A[i][0]>A[j][1]){
            ans.push_back(A[i][2]);
            j=i;
        }
    }
    return ans ;
}

根因定位 #

代码的贪心算法逻辑完全正确，性能问题来自无意义的内存拷贝开销：

• 排序函数的lambda比较器采用值传递接收两个vector参数：[](vector<int>A,vector<int>B)，每次执行比较逻辑时，都会完整拷贝两个长度为3的vector对象。排序的时间复杂度为O(nlogn)，当n规模较大时，海量的临时对象拷贝会消耗大量运行时间，直接触发TLE。

修复方案 #

将比较器的参数改为const引用传递，彻底消除拷贝开销，修改后的比较器代码如下：

sort(A.begin(),A.end(),[](const vector<int>& A, const vector<int>& B){
    if(A[1] != B[1]){
        return A[1] < B[1];
    }
    return A[2] < B[2];
});

可选优化：可以用结构体或三元组存储单场会议的开始时间、结束时间、编号三个属性，相比vector存储能进一步降低内存访问开销，但仅修改参数传递方式即可解决当前的TLE问题。

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