طول اجتماع پاره‌خط‌ها¶
$n$ پاره‌خط روی یک خط داده شده است که هر کدام با یک زوج مختصات $(a_{i1}, a_{i2})$ توصیف می‌شوند. باید طول اجتماع آن‌ها را پیدا کنیم.
الگوریتم زیر توسط Klee در سال ۱۹۷۷ ارائه شد. این الگوریتم در زمان $O(n\log n)$ اجرا می‌شود و ثابت شده است که از نظر مجانبی بهینه است.
راه حل¶
نقاط ابتدایی و انتهایی تمام پاره‌خط‌ها را در یک آرایه به نام $x$ ذخیره می‌کنیم. علاوه بر مختصات هر نقطه، نوع آن (اینکه نقطه شروع پاره‌خط است یا پایان) را نیز ذخیره می‌کنیم. سپس این آرایه را بر اساس مقدار مختصات نقاط مرتب می‌کنیم.
حالا روی آرایهٔ مرتب‌شده پیمایش می‌کنیم و یک شمارنده $c$ برای نگهداری تعداد پاره‌خط‌های باز (فعال) در نظر می‌گیریم. هرگاه نقطهٔ فعلی، نقطهٔ شروع یک پاره‌خط باشد، شمارنده را یکی اضافه می‌کنیم و در غیر این صورت (اگر نقطهٔ پایان باشد)، آن را یکی کم می‌کنیم. برای محاسبهٔ پاسخ، فاصلهٔ بین مختصات فعلی و قبلی ($x_i - x_{i-1}$) را در نظر می‌گیریم. اگر قبل از پردازش نقطهٔ فعلی، شمارنده $c$ بزرگتر از صفر بوده باشد (به این معنی که بازهٔ بین $x_{i-1}$ و $x_i$ پوشانده شده است)، این فاصله را به جواب نهایی اضافه می‌کنیم.
پیاده‌سازی¶
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;
}