রেখাংশের ইউনিয়নের দৈর্ঘ্য#

একটি সরলরেখায় $n$টি রেখাংশ দেওয়া আছে, প্রতিটি স্থানাঙ্কের একটি জোড়া $(a_{i1}, a_{i2})$ দ্বারা বর্ণিত। আমাদের তাদের ইউনিয়নের দৈর্ঘ্য বের করতে হবে।

নিম্নলিখিত অ্যালগরিদমটি Klee ১৯৭৭ সালে প্রস্তাব করেছিলেন। এটি $O(n\log n)$-তে কাজ করে এবং প্রমাণিত হয়েছে যে এটি অ্যাসিম্পটোটিকভাবে সর্বোত্তম।

সমাধান#

আমরা একটি অ্যারে $x$-তে সব রেখাংশের প্রান্তবিন্দু তাদের মান অনুসারে সর্ট করে সংরক্ষণ করি। এবং অতিরিক্তভাবে সংরক্ষণ করি এটি একটি রেখাংশের বাম প্রান্ত না ডান প্রান্ত। এখন আমরা অ্যারের উপর ইটারেট করি, বর্তমানে খোলা রেখাংশের একটি কাউন্টার $c$ বজায় রেখে। যখনই বর্তমান এলিমেন্ট একটি বাম প্রান্ত, আমরা এই কাউন্টার বাড়াই, অন্যথায় কমাই। উত্তর গণনা করতে, আমরা শেষ দুটি $x$ মানের মধ্যে দৈর্ঘ্য $x_i - x_{i-1}$ নিই, যখনই আমরা একটি নতুন স্থানাঙ্কে আসি, এবং বর্তমানে অন্তত একটি রেখাংশ খোলা থাকে।

ইমপ্লিমেন্টেশন#

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;
}