Short C++ Sweep Line

• ``````    bool isRectangleCover(vector<vector<int>>& rectangles) {
vector<vector<int>> edges;
int minx=INT_MAX, miny=INT_MAX, maxx=INT_MIN, maxy=INT_MIN;
int sum = 0;
for(auto &a:rectangles) {
edges.push_back({a[0],1,a[1],a[3]});
edges.push_back({a[2],-1,a[1],a[3]});
sum+=(a[2]-a[0])*(a[3]-a[1]);
minx = min(minx, a[0]);
maxx = max(maxx, a[2]);
miny = min(miny, a[1]);
maxy = max(maxy, a[3]);
}
sort(edges.begin(), edges.end());
set<pair<int,int>> st;
for(auto &a:edges) {
if(a[1]<0) st.erase({a[2],a[3]});
else {
auto it = st.lower_bound({a[2],a[3]});
if(it!=st.end() && it->first<a[3]) return false;
if(it!=st.begin() && (--it)->second>a[2]) return false;
st.insert({a[2],a[3]});
}
}
return sum==(maxy-miny)*(maxx-minx);
}
``````

• @buaaroger said in Short C++ Sweep Line:

``````    bool isRectangleCover(vector<vector<int>>& rectangles) {
vector<vector<int>> edges;
int minx=INT_MAX, miny=INT_MAX, maxx=INT_MIN, maxy=INT_MIN;
int sum = 0;
for(auto &a:rectangles) {
edges.push_back({a[0],1,a[1],a[3]});
edges.push_back({a[2],-1,a[1],a[3]});
sum+=(a[2]-a[0])*(a[3]-a[1]);
minx = min(minx, a[0]);
maxx = max(maxx, a[2]);
miny = min(miny, a[1]);
maxy = max(maxy, a[3]);
}
sort(edges.begin(), edges.end());
set<pair<int,int>> st;
for(auto &a:edges) {
if(a[1]<0) st.erase({a[2],a[3]});
else {
auto it = st.lower_bound({a[2],a[3]});
if(it!=st.end() && it->first<a[3]) return false;
if(it!=st.begin() && (--it)->second>a[2]) return false;
st.insert({a[2],a[3]});
}
}
return sum==(maxy-miny)*(maxx-minx);
}
``````

can you explain what this code is doing?

why are 1 and -1 being pushed as coordinates in the following?

edges.push_back({a[0],1,a[1],a[3]});
edges.push_back({a[2],-1,a[1],a[3]});

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.