Algorithm O(n log n) to identify contiguous intervals given a range list

Question

I have the following problem: Given a list with n continuous intervals, return a list of m continuous intervals such that:

• every point of the entry list is contained in any of the intervals of the second list
• every point of the output list is at least one entry list item
• there is no intersection between the elements of the output list

Examples of input and output:

-- Entrada
1-3
2-6
7-10

-- Saída
1-6
7-10

-- Entrada
1-3
2-8
7-10

-- Saída
1-10

-- Entrada
1-3
4-7
8-10

-- Saída
1-3
4-7
8-10

Entry and exit order are irrelevant.

This problem is equivalent to finding out how many related components have an interval graph, presented only the vertices/ranges of that graph, and what the interval represented by each related component.

The strategy I could think of follows a quadratic logic. It follows a pseudo-code in Java:

List<Intervalo> entrada = ...;
ArrayList<Intervalo> saída = new ArrayList<>();

processaEntrada: for (Intervalo intervaloEntrada: entrada) {
  Integer firstNullPosition = null;
  Intervalo intervaloInserido = intervaloEntrada.copia();
  ArrayList<Integer> índicesInterseção = new ArrayList<>();
  for (int i = 0; i < saída.length(); i++) {
    Intervalo intervaloJulgamento = saída.get(i);
    if (intervaloJulgamento == null) {
      if (firstNullPosition == null) {
        firstNullPosition = i;
      }
      continue;
    }
    // como a lista  saida só contém elementos sem interseção entre si,
    // é impossível que seja possível que essa comparação e a de alguma 
    // interseção com outro elemento de saida aconteçam
    if (intervaloJulgamento.contemIntervalo(intervaloInserido) {
      continue processaEntrada;
    }
    if (háInterseção(intervaloJulgamento, intervaloInserido)) {
      índicesInterseção.add(i);
    }
  }
  // se índicesInterseção for não vazio, então houve alguma interseção
  // caso contrário não houve interseção e, portanto, o intervaloInserido está
  // pronto para ser adicionado na lista
  if (índicesInterseção.isEmpty()) {
    if (firstNullPosition != null) {
      saída.set(firstNullPosition, intervaloInserido);
    } else {
      saída.add(intervaloInserido);
    }
  } else {
    Intervalo intervaloInterseções = intervaloInserido;
    int idxInserção = índicesInterseção.get(0);
    for (Integer i: índicesInterseção) {
      Intervalo interseptado = saída.get(i);
      saída.set(i, null);
      intervaloInterseções.começo = min(intervaloInterseções.começo, interseptado.começo);
      intervaloInterseções.fim = max(intervaloInterseções.fim, interseptado.fim);
    }
    saída.set(idxInserção, intervaloInterseções);
  }
}

return saída.stream().filter(Objects::nonNull).collect(Collectors.toList());

Answer 1

The Java code I’ve built is as follows:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Victor Williams Stafusa da Silva
 */
public class Main {
    public static void main(String[] args) {
        System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(2, 6), new Intervalo(7, 10)));
        System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(2, 8), new Intervalo(7, 10)));
        System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(4, 7), new Intervalo(8, 10)));
        System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(3, 10)));
    }
}

final class Intervalo {
    private final double a;
    private final double b;

    public Intervalo(double a, double b) {
        if (b < a) throw new IllegalArgumentException();
        this.a = a;
        this.b = b;
    }

    public double getA() {
       return a;
    }

    public double getB() {
       return b;
    }

    @Override
    public String toString() {
        return "[" + a + "<->" + b + "]";
    }

    public Evento getEventoA() {
        return new Evento(true, a);
    }

    public Evento getEventoB() {
        return new Evento(false, b);
    }

    @SafeVarargs
    public static List<Intervalo> reduzir(Intervalo... lista) {
        return reduzir(List.of(lista));
    }

    public static List<Intervalo> reduzir(List<Intervalo> lista) {
        List<Evento> eventos = new ArrayList<>(lista.size() * 2);
        for (Intervalo i : lista) {
            eventos.add(i.getEventoA());
            eventos.add(i.getEventoB());
        }
        Collections.sort(eventos);
        List<Intervalo> saida = new ArrayList<>(lista.size());
        int contagem = 0;
        double inicio = Double.NEGATIVE_INFINITY;
        for (Evento e : eventos) {
            if (e.isInicioIntervalo()) {
                if (contagem == 0) inicio = e.getPonto();
                contagem++;
            } else {
                contagem--;
                if (contagem == 0) saida.add(new Intervalo(inicio, e.getPonto()));
            }
        }
        return saida;
    }
}

final class Evento implements Comparable<Evento> {
    private final boolean inicioIntervalo;
    private final double ponto;

    public Evento(boolean inicioIntervalo, double ponto) {
        this.inicioIntervalo = inicioIntervalo;
        this.ponto = ponto;
    }

    public boolean isInicioIntervalo() {
        return inicioIntervalo;
    }

    public double getPonto() {
        return ponto;
    }

    @Override
    public int compareTo(Evento outro) {
        return this.ponto < outro.ponto ? -1
                : this.ponto > outro.ponto ? 1
                : this.inicioIntervalo == outro.inicioIntervalo ? 0
                : this.inicioIntervalo ? -1
                : 1;
    }
}

Let’s see what is the complexity of the static method reduzir:

        List<Evento> eventos = new ArrayList<>(lista.size() * 2);

That is O(n). Note that I gave an exact size to the list (2n) enough that it never needs to be resized. The method size() is O(1).

        for (Intervalo i : lista) {
            eventos.add(i.getEventoA());
            eventos.add(i.getEventoB());
        }

The getters are O(1). The method add is O(1) if the list does not need to be resized (and it never will). The number of Eventos created in the list is 2n.

        Collections.sort(eventos);

Ordination is O(Tn log n), where t is the complexity of the method compareTo class Evento. How this method has complexity O(1), then it boils down to O(n log n). This is the point that makes the algorithm have such complexity.

        List<Intervalo> saida = new ArrayList<>(lista.size());

Again is O(n) and never need to be resized, because the worst case is precisely when none of the intervals overlaps with the others.

        int contagem = 0;
        double inicio = Double.NEGATIVE_INFINITY;

That’s right O(1).

        for (Evento e : eventos) {
            if (e.isInicioIntervalo()) {
                if (contagem == 0) inicio = e.getPonto();
                contagem++;
            } else {
                contagem--;
                if (contagem == 0) saida.add(new Intervalo(inicio, e.getPonto()));
            }
        }

Whereas the number of events is 2n, so this one for is also O(n).

The methods isInicioIntervalo, getPonto, add (whereas saida will never need to be resized) and the Intervalo are also all O(1).

        return saida;

That is O(1).

Basically the algorithm reduces itself to undoing the intervals and marking them as an ordered sequence of points, where each point corresponding to the beginning of an interval sum 1 in contagem and each point equivalent to the end subtracts 1 of contagem.

When contagem comes out of zero, it’s because we’re in some gap that opened.

While contagem is greater than zero, there are open intervals colliding with each other. And the number of contagem tells exactly how many.

When contagem is reduced to zero, means that all the open intervals have closed and we can then add a large interval corresponding to all of this, from the point where this variable left from zero to the point where it returned to it.

The complexity of the algorithm is dominated by ordering, which is the most complex operation (O(n log n)).

Since the elements in the list eventos are properly ordered, this ensures that the elements of saida will also be correct and properly ordered.

It is also worth paying attention to the method compareTo:

    public int compareTo(Evento outro) {
        return this.ponto < outro.ponto ? -1
                : this.ponto > outro.ponto ? 1
                : this.inicioIntervalo == outro.inicioIntervalo ? 0
                : this.inicioIntervalo ? -1
                : 1;
    }

He’s like that to make sure Eventos with smaller numbers will always precede those with greater numbers. And in the event of a tie, that an interval opening event always takes precedence over a closing one. This serves to ensure that intervals that are only touching (e.g., [1-3] and [3-10]) are considered as a collision.

If it is desired that events that are only touching are not considered as a collision, simply change the ? -1 : 1; of the end by ? 1 : -1;.

Considering these entry intervals:

System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(2, 6), new Intervalo(7, 10)));
System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(2, 8), new Intervalo(7, 10)));
System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(4, 7), new Intervalo(8, 10)));
System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(3, 10)));

Here is the output produced:

[[1.0<->6.0], [7.0<->10.0]]
[[1.0<->10.0]]
[[1.0<->3.0], [4.0<->7.0], [8.0<->10.0]]
[[1.0<->10.0]]

See here working on IDEONE.