区间有关问题
求最大重叠区间
有\(n\)个区间，求任意两个区间最大的重叠部分。
解法
首先把所有区间按左端点从小到大排序。设\(mx\)是前若干个区间的右端点最大能达到的值，对于每一个区间，设它的左端点为\(l\)，右端点为\(r\)，则其它区间与它的最大重叠部分为\(min(mx, r)-l\)，遍历每个区间，维护答案。
总的时间复杂度为\(O(nlog_{}{n})\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> s(n);
for(int i = 0; i < n; i++) {
cin >> s[i].first >> s[i].second;
}
sort(s.begin(), s.end());
int ans = 0, mx = s[0].second;
for(int i = 1; i < n; i++) {
ans = max(ans, min(mx, s[i].second) - s[i].first);
mx = max(mx, s[i].second);
}
cout << ans << "\n";
return 0;
}