51Nod-1091 线段的重叠 题解

线段的重叠

题目概述

给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。

思路分析

对这些线段优先按照左端点升序排序

枚举每条线段，记录枚举过的线段能到达的最远距离

对于每条线段，如果有重叠，计算重叠的长度最大值

重叠长度的计算方式为：max(最远右端点, 当前右端点)- 当前左断点

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
llong n, m, x;

struct Node {
    llong l, r;
    Node(llong l = 0, llong r = 0) : l(l), r(r) { }
    bool operator < (Node a) {
        if (l == a.l)   return r < a.r;
        return l < a.l;
    }
};
vector<Node> v;

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        llong l, r; cin >> l >> r;
        v.emplace_back(Node(l, r));
    }
    sort(v.begin(), v.end());
    llong ans = 0, id = 0;
    for (int i = 1; i < n; i++) {
        if (v[i].l < v[id].r) {
            ans = max(ans, min(v[id].r, v[i].r) - max(v[id].l, v[i].l));
        }
        if (v[i].r > v[id].r) {
            id = i;
        } 
    }
    cout << ans << "\n";
    return 0;
}