I'm trying to solve this problem on Leetcode: https://leetcode.com/problems/merge-intervals
I simply got a simple idea: sort the input and do the merge.
Here is my code:
vector<vector<int>> merge(vector<vector<int>> &intervals)
{
vector<vector<int>> res;
if (intervals.empty()) {
return res;
}
std::sort(intervals.begin(), intervals.end(), [](const vector<int> e1, const vector<int> e2) {
if (e1[0] == e2[0]) {
return e1[1] <= e2[1]; // ERROR!!!
}
return e1[0] < e2[0];
});
res.push_back(intervals[0]);
for (size_t i = 1; i < intervals.size(); i++) {
if (res.back()[1] >= intervals[i][0]) {
if (res.back()[1] <= intervals[i][1]) {
res.back()[1] = intervals[i][1];
}
} else {
res.push_back(intervals[i]);
}
}
return res;
}
In fact the error comes from the line of std::sort.
When I execute the code on Leetcode, I get an error:
Line 1052: Char 9: runtime error: reference binding to null pointer of type 'const __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' (aka 'const int') (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1061:9
But If I change the comparator as below:
std::sort(intervals.begin(), intervals.end(), [](const vector<int> e1, const vector<int> e2) {
if (e1[0] == e2[0]) {
return e1[1] < e2[1]; // change <= into <
}
return e1[0] < e2[0];
});
It will work as expected without any error.
I don't know why.
Aucun commentaire:
Enregistrer un commentaire