本文共 1175 字，大约阅读时间需要 3 分钟。

区间并集

描述：

求 a1 ∪ a2 ∪ a3 ∪ …… ∪ an。

输入：

第一行正整数 n 表示区间的个数。(1 <= n <= 1e5)

然后是 n 行，每行包含两个正整数 L 和 R，分别表示一个区间左右端点，即 [ L，R ]。(0 <= L <= R <= 1e10)

输出：

每个区间的左端点和右端点之间用空格隔开，每次输出以后都要换行。

样例输入：

1 2

1 4

8 10

8 9

5 6

6 7

样例输出：

5 7

8 10

HINT：

[5，6] 区间和 [6，7] 区间取并集后变为 [5，7]

[8，9] 区间和 [8，10] 区间取并集后变为 [8，10]

分析：

#include
   
    #include
    
     #include
     
      using namespace std;typedef long long ll;struct point//结构体{
   	ll l;	ll r;}a[100000];bool cmp(point x, point y)//快排{
   	if (x.l == y.l)return x.r < y.r;	else return x.l < y.l;}int main(){
   	int n;	cin >> n;	for (int i = 0; i < n; i++)	{
   		cin >> a[i].l >> a[i].r;	}	sort(a, a + n, cmp);//快排	for (int i = 1; i < n; i++)	{
   		if (a[i].l <= a[i - 1].r)		{
   			a[i].l = min(a[i - 1].l, a[i].l);			a[i].r = max(a[i - 1].r, a[i].r);			a[i - 1].l = -1;//标记			a[i - 1].r = -1;		}	}	for (int i = 0; i < n; i++)	{
   		if (a[i].l != -1 && a[i].r != -1)		{
   			cout << a[i].l <<" "<< a[i].r << endl;		}	}}
     
    
   

转载地址：https://blog.csdn.net/YYDS777/article/details/114488781 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！