如何提高 c++ 代码的运行时效率

Question

我正在做一个leetcode问题986。Interval List Intersections，我不知道为什么我的O(m+n(解决方案，即使是官方解决方案，在运行时也只能击败5%的提交。其他人是如何让它跑得更快的？有什么方法或建议可以改进我的代码吗？非常感谢。

class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> res;
int i = 0, j = 0;
while(i < A.size() && j < B.size()) {
int lo = max(A[i][0], B[j][0]);
int hi = min(A[i][1], B[j][1]);
if(lo <= hi) {
vector<int> temp{lo, hi};
res.push_back(temp);
}
if(A[i][1] <= B[j][1]) 
++i;
else
++j;
}
return res;
}
};

Answer 1

好的，我已经帮你做了。请参阅我在代码中的注释。

class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> res;
// Avoid reallocations, reserve enough memory.
res.reserve(A.size() + B.size());
int i = 0, j = 0;
// Hint to the compiler: A.size() and B.size() are immutable.
const int ii = A.size(), jj = B.size();
while(i < ii && j < jj) {
const int lo = max(A[i][0], B[j][0]);
const int hi = min(A[i][1], B[j][1]);
if(lo <= hi) {
// Construct inner vector in-place.
res.push_back(std::vector<int>({lo, hi}));
}
if(A[i][1] <= B[j][1]) 
++i;
else
++j;
}
return res;
}
};

结果：

运行时间：56毫秒，比间隔列表交集的46.23%的C++在线提交快。

内存使用率：13 MB，不到间隔列表交叉点C++在线提交的100.00%。

接受56毫秒13 MB cpp