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

একটি সরলরেখায় $n$টি রেখাংশ (segment) দেওয়া আছে, প্রতিটি স্থানাঙ্কের একটি জোড়া $(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;
}