LeetCode – Flujo de datos como intervalos separados (Java)

Dada una entrada de flujo de datos de enteros no negativos a1, a2, …, an, …, resuma los números vistos hasta ahora como una lista de intervalos disjuntos.

Por ejemplo, suponga que los números enteros del flujo de datos son 1, 3, 7, 2, 6, …, entonces el resumen será:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Hacer un seguimiento:
¿Qué sucede si hay muchas fusiones y el número de intervalos disjuntos es pequeño en comparación con el tamaño del flujo de datos?

Análisis

Podemos almacenar el intervalo en una matriz y cada iterador de tiempo sobre la matriz y fusionar el nuevo valor con un intervalo existente. Esto lleva tiempo O (n). Si hay muchas fusiones, queremos hacerlo en log (n).

Podemos resolver este problema usando un conjunto de árboles. El método floor () devuelve el elemento más grande de este conjunto menor o igual que el elemento dado, o nulo si no existe tal elemento. El método mayor () devuelve el elemento mínimo en este conjunto estrictamente mayor que el elemento dado, o nulo si no existe tal elemento. Nota: usamos mayor () en lugar de techo () para excluir el elemento dado.

Solución Java

public class SummaryRanges {
 
    TreeSet<Interval> set;
 
    /** Initialize your data structure here. */
    public SummaryRanges() {
        set = new TreeSet<Interval>(new Comparator<Interval>(){
            public int compare(Interval a, Interval b){
                return a.start-b.start;
            }
        });
    }
 
    public void addNum(int val) {
        Interval t = new Interval(val, val);
 
        Interval floor = set.floor(t);
        if(floor!=null){
            if(val<=floor.end){
                return;
            }else if(val == floor.end+1){
                t.start = floor.start;
                set.remove(floor);
            }
        }
 
        Interval ceil = set.higher(t);
        if(ceil!=null){
            if(ceil.start==val+1){
                t.end = ceil.end;
                set.remove(ceil);
            }
        }
 
        set.add(t);
    }
 
 
    public List<Interval> getIntervals() {
        return new ArrayList(set); 
        //Arrays.asList(set.toArray(new Interval[0]));
    }
}