E075. Длина объединения отрезков на прямой за O (N log N)

emaxx algorithm

#algorithm#emaxx#graph#range-query#segment-tree

Task

Источник: e-maxx.ru/algo, страница PDF 225.

Даны N отрезков на прямой, т.е. каждый отрезок задаётся парой координат (X1, X2). Рассмотрим объединение этих отрезков и найдём его длину. Алгоритм был предложен Кли (Klee) в 1977 году. Алгоритм работает за O (N log N). Было доказано, что этот алгоритм является быстрейшим (асимптотически).

Описание

Положим все координаты концов отрезков в массив X и отсортируем его по значению координаты. Дополнительное условие при сортировке - при равенстве координат первыми должны идти левые концы. Кроме того, для каждого элемента массива будем хранить, относится он к левому или к правому концу отрезка. Теперь пройдёмся по всему массиву, имея счётчик C перекрывающихся отрезков. Если C отлично от нуля, то к результату добавляем разницу Xi - Xi-1. Если текущий элемент относится к левому концу, то увеличиваем счётчик C, иначе уменьшаем его.

Реализация

unsigned segments_union_measure (const vector <pair <int,int> > & a) {

unsigned n = a.size();

vector <pair <int,bool> > x (n*2);

for (unsigned i=0; i<n; i++)

{

x[i*2] = make_pair (a[i].first, false);

x[i*2+1] = make_pair (a[i].second, true);

}

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

unsigned result = 0;

unsigned c = 0;

for (unsigned i=0; i<n*2; i++)

{

if (c && i)

result += unsigned (x[i].first - x[i-1].first);

if (x[i].second)

++c;

else

--c;

}

return result;

}

C# solution

auto-draft, review before submit

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    unsigned segments_union_measure (const vector <pair <int,int> > & a)
    {
            unsigned n = a.size();
            vector <pair <int,bool> > x (n*2);
            for (unsigned i=0; i<n; i++)
            {
                    x[i*2] = make_pair (a[i].first, false);
                    x[i*2+1] = make_pair (a[i].second, true);
            }
            sort (x.begin(), x.end());
            unsigned result = 0;
            unsigned c = 0;
            for (unsigned i=0; i<n*2; i++)
            {
                    if (c && i)
                            result += unsigned (x[i].first - x[i-1].first);
                    if (x[i].second)
                            ++c;
                    else
                            --c;
            }
            return result;
    }
}

C++ solution

matched/original

unsigned segments_union_measure (const vector <pair <int,int> > & a)
{
        unsigned n = a.size();
        vector <pair <int,bool> > x (n*2);
        for (unsigned i=0; i<n; i++)
        {
                x[i*2] = make_pair (a[i].first, false);
                x[i*2+1] = make_pair (a[i].second, true);
        }
        sort (x.begin(), x.end());
        unsigned result = 0;
        unsigned c = 0;
        for (unsigned i=0; i<n*2; i++)
        {
                if (c && i)
                        result += unsigned (x[i].first - x[i-1].first);
                if (x[i].second)
                        ++c;
                else
                        --c;
        }
        return result;
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    unsigned segments_union_measure (const vector <pair <int,int> > & a)
    {
            unsigned n = a.size();
            vector <pair <int,boolean> > x (n*2);
            for (unsigned i=0; i<n; i++)
            {
                    x[i*2] = make_pair (a[i].first, false);
                    x[i*2+1] = make_pair (a[i].second, true);
            }
            sort (x.begin(), x.end());
            unsigned result = 0;
            unsigned c = 0;
            for (unsigned i=0; i<n*2; i++)
            {
                    if (c && i)
                            result += unsigned (x[i].first - x[i-1].first);
                    if (x[i].second)
                            ++c;
                    else
                            --c;
            }
            return result;
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.