vector<int> smallestRange(vector<vector<int>>& nums) {
using vit = decltype(nums[0].begin());
using pit = pair<vit, vit>;
multiset<pair<int, pit>> window;
for(vector<int> vec: nums) window.insert({vec.front(), {vec.begin(), vec.end()}});
int lo = window.begin()->first;
int hi = window.rbegin()->first;
while(true) {
auto [vit, end] = window.begin()->second;
++vit;
if(vit == end) break;
window.erase(window.begin());
window.insert({(*vit), {vit, end}});
int i = window.begin()->first;
int j = window.rbegin()->first;
int dist = j - i;
if(dist >= 0 && dist < hi - lo) {
lo = i;
hi = j;
}
}
return {lo, hi};
}
What am I missing about Iterators? Are multiset iterators changed or invalidated on erase? The code finds the smallest range given a list of vectors sorted in nondecreasing order. I maintain a multiset to track elements from each list ordered. Remove the smallest, adding its next element while calculating the range.