上海市计算机学会竞赛平台2023年2月月赛丙组区间的并
发布时间
阅读量：
阅读量
题目描述
给定一个数轴上的 𝑛n 个闭区间，第 𝑖i 个闭区间的两端点为[𝑎𝑖,𝑏𝑖][ai,bi]，它们的并集可以表示为若干不相交的闭区间，请按照左端点从小到大的顺序输出这些区间的并集。
输入格式
- 第一行：单个整数 𝑛n；
- 第二行到第 𝑛+1n+1 行：每行两个整数 𝑎𝑖ai 与 𝑏𝑖bi 表示一个闭区间 [𝑎𝑖,𝑏𝑖][ai,bi]。
输出格式
若干行：表示输入区间的并集。每行两个整数，表示一个闭区间的两个端点，这些闭区间应该按照起点从小到大排序。
数据范围
- 对于 50%50% 的数据，1≤𝑛≤1041≤n≤104，0≤𝑎𝑖≤𝑏𝑖≤1040≤ai≤bi≤104
- 对于 100%100% 的数据，1≤𝑛≤1051≤n≤105，0≤𝑎𝑖≤𝑏𝑖≤1090≤ai≤bi≤109
样例数据
输入:
3
10 12
1 3
2 5
输出:
1 5
10 12
详见代码:
#include<bits/stdc++.h>
using namespace std;
struct st
{
int a;
int b;
};
struct st s[100005];
bool cmp(struct st x, struct st y)
{
if (x.a == y.a) return x.b < y.b;
return x.a < y.a;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i].a >> s[i].b;
}
sort(s + 1, s + n + 1, cmp);
int l, r;
l = s[1].a;
r = s[1].b;
for (int i = 2; i <= n; i++)
{
if (s[i].a <= r)
{
r = max(r,s[i].b);
}
else
{
cout << l << " " << r << endl;
l = s[i].a;
r = s[i].b;
}
}
cout << l << " " << r << endl;
return 0;
}
全部评论 (0)
还没有任何评论哟~