Unisci array con valori sovrapposti

Question

Im using Node.js. (... e underscore.js)

Considerate questa struttura dati

var numbers = [ 
    [10, 20] 
    [30, 40] 
    [40, 50] 
    [45, 70] 
    ... //Possibly more arrays (always contains two numbers) 
] 

numbers contengono matrici che contengono sempre coppie di numeri. Pensa a queste coppie di numeri come "inizio" e "fine". Voglio una funzione che consideri numbers come argomento, e faccia un ciclo attraverso il suo contenuto, e se il numero "di inizio" di una coppia si sovrappone al numero di "fine" della coppia precedente, questi array sono uniti in uno solo. Per esempio, questo:

var numbers = [ 
    [10, 20] 
    [19, 40] 
    [40, 60] 
    [70, 80] 
] 

Diventa questo:

var numbers = [ 
    [10, 60] // First, second and third array is merged because of overlapping . 
    [70, 80] 
] 

In realtà, ho già scritto una funzione per questo che funziona bene, ma si sente un po 'goffo.

Sono curioso di sapere se qualche javascript wizard può stupirmi con una soluzione super elegante =).

Answer 1

Creare un vuoto "risultato "array. Passa sopra l'array di intervalli e cambia l'ultimo elemento del risultato o aggiungi l'intervallo corrente.

function merge(ranges) { 
 
    var result = [], last; 
 

 
    ranges.forEach(function (r) { 
 
     if (!last || r[0] > last[1]) 
 
      result.push(last = r); 
 
     else if (r[1] > last[1]) 
 
      last[1] = r[1]; 
 
    }); 
 

 
    return result; 
 
} 
 

 
r = [[10, 20], [19, 40], [40, 60], [70, 80]]; 
 
document.write(JSON.stringify(merge(r)));

Ciò presuppone che la matrice di origine è ordinato, se non è sempre il caso, sorta prima fusione:

ranges.sort(function(a, b) { return a[0]-b[0] || a[1]-b[1] }); 

Answer 2

ho creato una funzione che fa quello che si vuole:

function merge(arr) { 
    // copy and sort the array 
    var result = arr.slice().sort(function(a, b) { 
      return a[0] > b[0]; 
     }), 
     i = 0; 

    while(i < result.length - 1) { 
     var current = result[i], 
      next = result[i+1]; 

     // check if there is an overlapping 
     if(current[1] >= next[0]) { 
      current[1] = Math.max(current[1], next[1]); 
      // remove next 
      result.splice(i+1, 1); 
     } else { 
      // move to next 
      i++; 
     } 
    } 
    return result; 
}; 

Questa funzione può essere utilizzata in questo modo:

var mergedNumbers = merge(numbers); 

DEMO

Answer 3

Come detto @Brett, questo potrebbe essere un meglio adattarsi per Code Review (assicurati di includere la tua attuale implementazione). Se pubblichi lì, metti un riferimento ad esso qui da qualche parte e sposterò la mia risposta.

---

Supponendo che l'array numbers è già ordinato correttamente, questa funzione dovrebbe fare quello che vuoi:

function combine(numbers) { 
 
    return numbers.reduce(function(combined, next) { 
 
     if (!combined.length || combined[combined.length-1][1] < next[0]) combined.push(next); 
 
     else { 
 
      var prev = combined.pop(); 
 
      combined.push([prev[0], Math.max(prev[1], next[1])]); 
 
     } 
 
    \t return combined; 
 
    }, []); 
 
} \t \t 
 

 
var n = [[10, 20], [19, 40], [40, 60], [70, 80], [75, 76]]; 
 
var r = combine(n); 
 
document.write('<pre>' + JSON.stringify(r) + '</pre>');

Questa "reduce s" la matrice originale a quella nuova utilizzando la seguente logica nella funzione di riduzione:

1. Se questo è il primo passaggio o l'ultimo elemento non si sovrappone all'elemento corrente, push l'elemento corrente sull'array combined.
2. Altrimenti:
   1. pop l'ultimo elemento dell'array fuori combined.
   2. push la combinazione dell'ultimo elemento e dell'articolo corrente sull'array combined.