两种合并区间的方法,为何一个对,一个错?
1.AC:
#include <bits/stdc++.h>
using namespace std;
/*都一样*/
struct Node{
ll a, b;
} rgn1[N], rgn2[N];
bool cmp(Node x, Node y){ return x.b < y.b || x.b == y.b && x.a > y.a; }
int main(){
/*都一样*/
sort(rgn1 + 1, rgn1 + tot + 1, cmp); rgn2[len = 1] = rgn1[1];
for(int i = 2; i <= tot; i++) if(rgn1[i].a > rgn2[len].a){
if(rgn1[i].b <= rgn2[len].a) rgn2[len].a = rgn1[i].a;
else rgn2[++len] = rgn1[i];
}
/*都一样
return 0;
}
2.WA:
#include <bits/stdc++.h>
using namespace std;
/*都一样*/
struct Node{
ll a, b;
} rgn1[N], rgn2[N];
bool cmp(Node x, Node y){
return x.a < y.a || (x.a == y.a && x.b < y.b);
}
int main(){
/*都一样*/
for(int i = 1; i <= tot; i++){
rgn2[i].b = 1ll<<60;
}
sort(rgn1 + 1, rgn1 + tot + 1, cmp);
for(int i = 1; i <= tot; i++) if(rgn1[i].a > rgn1[i-1].a){
while(len && rgn1[i].b <= rgn2[len].a) len--; len++;
rgn2[len].a = rgn1[i].a, rgn2[len].b = min(rgn2[len].b, rgn1[i].b);
}
/*都一样*/
return 0;
}