Хэрчмүүдийн нэгдлийн урт¶

Шулуун дээр $n$ хэрчим өгөгдсөн, тус бүр нь $(a_{i1}, a_{i2})$ координатын хосоор тодорхойлогдоно. Бид тэдгээрийн нэгдлийн уртыг олох ёстой.

Дараах алгоритмыг 1977 онд Klee санал болгосон. Энэ нь $O(n\log n)$-д ажилладаг бөгөөд асимптотоор оновчтой болох нь батлагдсан.

Шийдэл¶

Бид $x$ массивт бүх хэрчмийн үзүүрийн цэгүүдийг утгаар нь эрэмбэлж хадгална. Мөн нэмж хэрчмийн зүүн үзүүр эсвэл баруун үзүүр эсэхийг хадгална. Одоо бид массивыг тойрч, одоогоор нээлттэй байгаа хэрчмүүдийн тоолуур $c$-г хөтөлнө. Одоогийн элемент зүүн үзүүр байх бүрд бид энэ тоолуурыг ихэсгэх ба эс бөгөөс багасгана. Хариултыг тооцоолохын тулд бид шинэ координат дээр ирэх бүрд, тэр үед дор хаяж нэг хэрчим нээлттэй байвал сүүлийн хоёр $x$ утгын хоорондох $x_i - x_{i-1}$ уртыг авна.

Implementation¶

int length_union(const vector<pair<int, int>> &a) {
    int n = a.size();
    vector<pair<int, bool>> x(n*2);
    for (int i = 0; i < n; i++) {
        x[i*2] = {a[i].first, false};
        x[i*2+1] = {a[i].second, true};
    }

    sort(x.begin(), x.end());

    int result = 0;
    int c = 0;
    for (int i = 0; i < n * 2; i++) {
        if (i > 0 && x[i].first > x[i-1].first && c > 0)
            result += x[i].first - x[i-1].first;
        if (x[i].second)
            c--;
        else
            c++;
    }
    return result;
}