本文主要是介绍51Nod - 1091 - 线段的重叠，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，[10 20]和[12 25]的重叠部分为[12 20]。
给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。
Input
第1行：线段的数量N(2 <= N <= 50000)。 第2 - N + 1行：每行2个数，线段的起点和终点。(0 <= s , e <= 10^9)
Output
输出最长重复区间的长度。
Input示例
5 1 5 2 4 2 8 3 7 7 9
Output示例
4
思路：先对结构体进行排序，起点不同时按起点降序排列，起点相同时按终点升序排列。然后维护一个最大的终点，寻找最大的重叠区间即可。
ACDAIMA：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{int s,e;
}a[50005];
bool cmp(node a,node b)
{return a.s == b.s ? a.e > b.e : a.s < b.s;
}
int main()
{int n;cin>>n;for(int i = 0; i < n; i++)cin >> a[i].s >> a[i].e;sort(a,a+n,cmp);int ans = 0;int bj = a[0].e;for(int i = 1; i < n; i++){ans = max(ans,min(a[i].e,bj)-a[i].s); //寻找最大的重叠区间bj = max(bj,a[i].e); //维护最大的终点}cout << ans << endl;
}
这篇关于51Nod - 1091 - 线段的重叠的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
