51nod 1091 線段的重疊 （貪心）

​​51nod 1091 線段的重疊​​

題目

分析

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const int N = 5e4 + 10;

int n;
struct node {
    int x, y;
    bool operator < (const node& b) const {
        if(x == b.x) return y > b.y;
        return x < b.x;
    }
}a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y; 
    }
    sort(a, a + n);
    int limit = -1, ans = 0;
    for (int i = 0; i < n; i++) {
        if (limit >= a[i].y) {
            ans = max(ans, a[i].y - a[i].x); 
        }
        if(limit > a[i].x && limit < a[i].y) {
            ans = max(ans, limit - a[i].x);
        }
        limit = max(limit, a[i].y);
    }
    cout << ans << "\n";
}