Здравствуйте, pASkuda, Вы писали:

AS>Вот собственно стоит такая задчка: есть массив закрытых интервалов, нужно объединить те которые имеют пересечение. Я налабал на шарпе, но это однозначно не оптимально, может кто знает более короткое решение (у гогля спрашивал – не нашел)

Берем все точки интервалов (начальные и конечные), сортируем их по возрастанию. При равных координатах сначала идут начальные точки. Дальше заводим счетчик, изначально равный нулю. Идем по всем точкам слева направо; когда встречаем начальную точку, увеличиваем счетчик на единицу, когда встречаем конечную, уменьшаем на единицу. Когда счетчик переходит из значения 0 в значение 1 — запоминаем текущую точку как начальную нового интервала. Когда наоборот, из 1 в 0 создаем интервал с началом в запомненной точке и концом в текущей и пихаем его в результат.

Здравствуйте, Vintik_69, Вы писали:

V_>Берем все точки интервалов (начальные и конечные), сортируем их по возрастанию. <...> Когда наоборот, из 1 в 0 создаем интервал с началом в запомненной точке и концом в текущей и пихаем его в результат.

Алгоритм хороший, но если интервалы уже упорядочены, например по левому краю, то слишком медленный...

Вот собственно стоит такая задчка: есть массив закрытых интервалов, нужно объединить те которые имеют пересечение. Я налабал на шарпе, но это однозначно не оптимально, может кто знает более короткое решение (у гогля спрашивал – не нашел)

public static DoubleInterval[] Merge(params DoubleInterval[] ranges)
{
    if (ranges == null)
    {
        throw new ArgumentNullException("ranges");
    }

    List<DoubleInterval> result = new List<DoubleInterval>();

    foreach (DoubleInterval range in ranges)
    {
        DoubleInterval newRange = new DoubleInterval(range.Minimum, range.Maximum);
        if (result.Count > 0)
        {
            Int32 index = result.Count - 1;
            while (index >= 0)
            {
                DoubleInterval prevRange = result[index];
                if (prevRange.CanMergeWith(newRange))
                {
                    newRange = prevRange.MergeWith(newRange);
                    result.RemoveAt(index);
                    index = result.Count - 1;
                    continue;
                }
                index--;
            }
        }
        result.Add(newRange);
    }
    return result.ToArray();
}

ну и соответственно

public class DoubleInterval
{
    public Double Minimum;
    public Double Maximum;
    public DoubleInterval MergeWith(DoubleInterval range)
    {
        if (!this.CanMergeWith(range))
        {
            throw new InvalidOperationException();
        }

        return new DoubleInterval(Math.Min(this.Minimum, range.Minimum), Math.Max(this.Maximum, range.Maximum));
    }
}

V_>Берем все точки интервалов (начальные и конечные), сортируем их по возрастанию. При равных координатах сначала идут начальные точки. Дальше заводим счетчик, изначально равный нулю. Идем по всем точкам слева направо; когда встречаем начальную точку, увеличиваем счетчик на единицу, когда встречаем конечную, уменьшаем на единицу. Когда счетчик переходит из значения 0 в значение 1 — запоминаем текущую точку как начальную нового интервала. Когда наоборот, из 1 в 0 создаем интервал с началом в запомненной точке и концом в текущей и пихаем его в результат.

ООО спасибо!!! ИТ ВОРКС!!!

Здравствуйте, Erop, Вы писали:

E>Алгоритм хороший, но если интервалы уже упорядочены, например по левому краю, то слишком медленный...

А какой ваш вариант?

Здравствуйте, pASkuda, Вы писали:

AS>А какой ваш вариант?
Зависит от упорядочения интервалов изначально. Если, например, они упорядочены по левым краям, то нужно ли их объединять решается просто. Если левый конец второго меньше правого конца первого, правый -- это максимум из правых концов обеих, а второй нужно выкинуть...

Если ты пишешь на C++ + STL, то что-то типа такого:

struct Range {
    int Begin;
    int End;
};

// Возвращает конец
template<typename It, typename ConstIt
It MergeLinkedRanges( It dst, ConstIt src, ConstIt srcEnd )
{
    if( src == srcEnd )
        return dst;
    for( *dst = *src++; src != srcEnd; ++src ) {    
        assert( dst->Begin <= src->Begin );
        if( dst->End < src->Begin ) {
            *++dst = *src;
            continue;
        } 
        if( dst->End < src->End ) { 
            dst->End = src->End;
        }
    }
    return ++dst;
}

inline void MergeLinkedRanges( std::vector<Range> dst ) 
    { dst.erase( MergeLinkedRanges( dst.begin(), dst.begin(), dst.end ), dst.end() ); }

Здравствуйте, Erop, Вы писали:

AS>>А какой ваш вариант?
E>Зависит от упорядочения интервалов изначально. Если, например, они упорядочены по левым краям, то нужно ли их объединять решается просто. Если левый конец второго меньше правого конца первого, правый -- это максимум из правых концов обеих, а второй нужно выкинуть...

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

Добрый день! это опять Я

Как наиболее быстро найти все пересечения двух коллекций интервалов?

Т.е. если есть две колеекции

 0  1  -1  1
 3  8   2  5
10 11   6  9

На выходе должно получиться, что то вроде этого:
0 1
3 5
6 8

зы: свой код приводить не будут т.к. он опять таки у меня совсем не оптимален (его я сделал на основе первого вариант объеденения интервалов, тока ввел признак у понита из первой колеекци он или из второй) !