Algoritmo para encontrar interseções de span em um conjunto ordenado

Eu tenho um conjunto de itens estritamente pedidos no prazo. Cada item pode ser único (sem Avançar, sem Anterior) ou parte de um intervalo (com 1 ou 2 pontos de extremidade adicionais). Por exemplo, na figura A faz parte de um intervalo de 3 elementos 1 - > 4 - > 5, B faz parte de uma extensão de 2 elementos 2 - > 3 e C faz parte de um intervalo de 2 elementos 6 - > 16. Como você pode ver, os espaços podem se sobrepor (start2 > start1, end1 > end2).

O que eu quero fazer é elaborar um algoritmo rápido para descobrir quais extensões (ou indivíduos) estão se cruzando em um determinado intervalo Min - > Max.

Minha abordagem ingênua é simplesmente testar cada item do conjunto, com algo como:

for(auto const & e : items)
{
    if(e.Previous)
    {
        // Middle or last item in a set (already been tested).

        continue;
    }

    auto t1 = e.Time, t2 = e.Time;

    if(e.Next)
    {           
        if(e.Next.Next)
        {
            // Part of a 3 item span (start, middle, end).

            t2 = e.Next.Next.Time;
        }
        else
        {
            // Part of a 2 item span (start, end).

            t2 = e.Next.Time;
        }
    }       

    if(t1 > MaxTime || t2 < MinTime)
    {
        // Does not intersect the span.

        continue;
    }       

    ... Do something with the item, such as draw it.
}

Isso não funciona muito mal com 250.000 itens, mas começa a ficar muito lento quando você chega a milhões.

Eu tenho muito tempo disponível na inicialização para obter um std: future instalado e em execução para pré-processar essas coisas em uma estrutura mais útil, se isso ajudar. Eu também preciso ser capaz de acrescentar ao final do conjunto, embora mantendo a ordem de tempo estritamente crescente (por exemplo, now () > = items.last (). Time).

Alguma coisa acontece com alguém?