Acwing 803.区间合并
题目描述
给定 nn 个区间 [lili,riri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[11,33] 和 [22,66] 可以合并为一个区间 [11,66] 。
输入格式
第一行包含整数nn。
接下来nn行，每行包含两个整数ll和rr。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤1000001≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109
样例
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
思路提示
可以先按左端点排序，再维护一个区间，与后面一个个区间进行三种情况的比较，存储到数组里去。
C++ 代码
#include #include #include using namespace std ; typedef pair<int,int> pii ; vector nums,res ; int main() { int st=-2e9,ed=-2e9 ; //ed代表区间结尾，st代表区间开头 int n ; scanf(“%d”,&n) ; while(n–) { int l,r ; scanf(“%d%d”,&l,&r) ; nums.push_back({l,r}) ; } sort(nums.begin(),nums.end()) ; //按左端点排序 for(auto num:nums) { if(ed<num.first) //情况1：两个区间无法合并 { if(ed!=-2e9) res.push_back({st,ed}) ; //区间1放进res数组 st=num.first,ed=num.second ; //维护区间2 } //情况2：两个区间可以合并，且区间1不包含区间2，区间2不包含区间1 else if(ed<num.second) ed=num.second ; //区间合并 } //(实际上也有情况3：区间1包含区间2，此时不需要任何操作，可以省略)
//注：排过序之后，不可能有区间2包含区间1 res.push_back({st,ed}); //考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。 //因为这是最后的一个序列，所以不可能继续进行合并。 /* for(auto r:res) printf("%d %d\n",r.first,r.second) ; puts("") ; */ //(把上面的注释去掉，可以在调试时用) printf("%d",res.size()) ; //输出答案 return 0 ;
}
Acwing 803.区间合并
题目描述
给定 nn 个区间 [lili,riri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[11,33] 和 [22,66] 可以合并为一个区间 [11,66] 。
输入格式
第一行包含整数nn。
接下来nn行，每行包含两个整数ll和rr。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤1000001≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109
样例
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
思路提示
可以先按左端点排序，再维护一个区间，与后面一个个区间进行三种情况的比较，存储到数组里去。
C++ 代码
#include #include #include using namespace std ; typedef pair<int,int> pii ; vector nums,res ; int main() { int st=-2e9,ed=-2e9 ; //ed代表区间结尾，st代表区间开头 int n ; scanf(“%d”,&n) ; while(n–) { int l,r ; scanf(“%d%d”,&l,&r) ; nums.push_back({l,r}) ; } sort(nums.begin(),nums.end()) ; //按左端点排序 for(auto num:nums) { if(ed<num.first) //情况1：两个区间无法合并 { if(ed!=-2e9) res.push_back({st,ed}) ; //区间1放进res数组 st=num.first,ed=num.second ; //维护区间2 } //情况2：两个区间可以合并，且区间1不包含区间2，区间2不包含区间1 else if(ed<num.second) ed=num.second ; //区间合并 } //(实际上也有情况3：区间1包含区间2，此时不需要任何操作，可以省略)
//注：排过序之后，不可能有区间2包含区间1 res.push_back({st,ed}); //考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。 //因为这是最后的一个序列，所以不可能继续进行合并。 /* for(auto r:res) printf("%d %d\n",r.first,r.second) ; puts("") ; */ //(把上面的注释去掉，可以在调试时用) printf("%d",res.size()) ; //输出答案 return 0 ;
}
