C++(clang++11) 解法, 执行用时: 7ms, 内存消耗: 424K, 提交时间: 2021-05-10 23:33:36

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    int l, n;
    cin >> l >> n;
    vector<pair<int, int>> jobs(n);
    for (auto &[a, b] : jobs) cin >> a >> b;
    ll ans = numeric_limits<ll>::max();
    for (int T = 0; T <= 1; T++) {
        int xmin = numeric_limits<int>::max();
        int xmax = numeric_limits<int>::min();
        vector<pair<int, int>> events;
        for (auto [a, b] : jobs) {
            xmin = min({xmin, a, b});
            xmax = max({xmax, a, b});
            if (a > b) {
                events.emplace_back(a, 1);
                events.emplace_back(b, -1);
            }
        }
        sort(events.begin(), events.end());
        int balance = 0, start = 0;
        vector<pair<int, int>> back_intervals;
        back_intervals.emplace_back(xmin, xmin);
        for (auto [x, add] : events) {
            if (balance == 0) start = x;
            balance += add;
            if (balance == 0) back_intervals.emplace_back(start, x);
        }
        back_intervals.emplace_back(xmax, xmax);
        ll best = xmin;
        for (auto [a, b] : back_intervals) {
            assert(2 * (xmax - xmin) > 0);
            ans = min(ans, 2 * (xmax - xmin) + best - a);
            best = min((ll)b, best + 2 * (b - a));
        }
        for (auto &[a, b] : jobs) a = -a, b = -b;
    }
    cout << ans << '\n';
    return 0;
}