Calcoli di intervalli di numeri in PHP

Question

e prima di tutto, grazie per aver dedicato del tempo a leggere la mia domanda.

Sto cercando di scrivere una sceneggiatura e ho riscontrato un problema che trovo difficile da risolvere. Sto lavorando con una coppia di numeri (ad esempio, 1000 e 2000) e ho una matrice di coppie di numeri:

$pairs = array(
    array(800, 1100),
    array(1500, 1600),
    array(1900, 2100)
)

Quello che sto cercando di trovare è come ottenere gli intervalli non coperti dalle coppie di numeri, tra 1000 e 2000. In questo esempio, 1000-1100 è coperto da array (800, 1100), 1500-1600 è coperto per array (1500, 1600) e 1900-2000 è coperto da array (1900, 2100), che mi lascia con 1101-1499 e 1599-1899 rimasti a coprire. Spero di essere abbastanza chiaro.

Quello che mi chiedo è come farei in modo che PHP mi restituisca un array di intervalli non coperti dalla variabile $ accoppiamenti. In questo esempio restituirebbe:

array(
    array(1101, 1499),
    array(1599, 1899)
)

Hai idea di quale sarebbe il modo migliore per farlo?

Grazie in anticipo.

Answer 1

Bene, innanzitutto devi definire il problema:

1. Le coppie sono ordinate?
2. Le coppie si sovrappongono?
3. Vuoi trovare gli intervalli mancanti per un intervallo particolare (questo sembra essere il caso)?

Se le coppie non sono ordinate, prima ordinale:

usort($pairs, 'cmp_pair');

function cmp_pair($a, $b) {
  if ($a[0] == $b[0]) {
    if ($a[1] == $b[1]) {
      return 0;
    } else {
      return $a[1] < $b[1] ? -1 : 1;
    }
  } else {
    return $a[0] < $b[0] ? -1 : 1;
  }
}

Se sono consentiti intervalli sovrapposti, trasforma l'elenco di coppie in un set non sovrapposto. Ecco un suggerimento su come farlo:

$prev = false;
$newpairs = array();
foreach ($pairs as $pair) {
  if ($prev) {
    // this also handles the case of merging two ranges
    // eg 100-199 with 200 to 250 to 100-250
    if ($prev[1] >= $pair[0]-1) {
      $prev = array($prev[0], max($prev[1], $pair[1]));
    } else {
      $newpairs[] = $prev;
    }
  }
  $prev = $pair;
}
$pairs = $newpairs;

Ora non ci dovrebbero essere coppie sovrapposte, quindi il problema diventa un po 'più semplice dato che hai anche un array ordinato.

function missing($start, $end, $pairs) {
  $missing = array();
  $prev = false;
  foreach ($pairs as $pair) {
    // if the current pair starts above the end, we're done
    if ($pair[0] > $end) {
      break;
    }

    // we can ignore any pairs that end before the start
    if ($pair[1] < $start) {
      continue;
    }

    // if the pair encompasses the whole range, nothing is missing
    if ($pair[0] <= $start && $pair[1] >= $end) {
      break;
    }

    // if this is our first overlapping pair and it starts above
    // the start we can backfill the missing range
    if ($pair[0] > $start && !$missing) {
      $missing[] = array($start, $pair[0]);
    }

    // compare this pair to the previous one (if there is one) and
    // fill in the missing range
    if ($prev) {
      $missing[] = array($prev[1]+1, $pair[0]-1);
    }

    // set the previous
    $prev = $pair;
  }

  // if this never got set the whole range is missing
  if (!$prev) {
    $missing[] = array($start, $end);

  // if the last overlapping range ended before the end then
  // we are missing a range from the end of it to the end of
  // of the relevant range
  } else if ($prev[1] < $end) {
    $missing[] = array($prev[1]+1, $end);
  }

  // done!
  return $missing;
}

Spero che sia d'aiuto.

Answer 2

Vorrei fare qualcosa del genere:

begin = 1000
end   = 2000
uncovered = ()
foreach pairs as pair
  if (pair[0] > begin)
    push (uncovered, begin, pair[0])
    begin = pair[1]
  end if
end foreach

Questa è solo un'idea, ma ecco il punto: Considera di avere un segmento grande (da 1000 a 2000) e uno piccolo. Volete ottenere ogni segmento di quello grande che non è coperto da quello piccolo. Immagina di avere una penna!

Init all'inizio. Scorrere su ciascun "piccolo segmento" hai. Se stai cercando (rigorosamente) l'inizio, allora c'è un "buco", quindi devi memorizzare che dall'inizio all'inizio del segmento corrente.

Spero che questo aiuti e che sia corretto!

Answer 3

// your original arrays of integers
$pairs = array(
    array(800, 1100),
    array(1500, 1600),
    array(1900, 2100)
);

// first, normalize the whole thing into a giant list of integers that
// are included in the array pairs, combine and sort numerically
$numbers_in_pairs = array();
foreach($pairs as $set) {
    $numbers_in_pairs = array_merge($numbers_in_pairs, range($set[0], $set[1]));
}
sort($numbers_in_pairs);

// find the min
$min = $numbers_in_pairs[0];

// find the max
$max = $numbers_in_pairs[count($numbers_in_pairs)-1];

Trova la differenza dell'array

// create an array of all numbers inclusive between the min and max
$all_numbers = range($min, $max);

// the numbers NOT included in the set can be found by doing array_diff
// between the two arrays, we need to sort this to assure no errors when
// we iterate over it to get the maxes and mins
$not_in_set = array_diff($all_numbers, $numbers_in_pairs);
sort($not_in_set);

Metadati sui set che useremo in seguito:

// gather metadata about the numbers that are not inside the set
// $not_in_set_meta['min'] = lowest integer
// $not_in_set_meta['max'] = highest integer
// $not_in_set_meta['mins'] = min boundary integer
// $not_in_set_meta['maxes'] = max boundary integer
$not_in_set_meta = array();
for($i=0;$i<count($not_in_set);$i++) {
    if ($i == 0) {
        $not_in_set_meta['min'] = $not_in_set[$i];
        $not_in_set_meta['mins'][] = $not_in_set[$i];
    } else if ($i == count($not_in_set)-1 ) {
        $not_in_set_meta['max'] = $not_in_set[$i];
        $not_in_set_meta['maxes'][] = $not_in_set[$i];
    } else {
        // in the event that a number stands alone
        // that it can be BOTH the min and the max
        if (($not_in_set[$i+1] - $not_in_set[$i]) > 1) {
            $not_in_set_meta['maxes'][] = $not_in_set[$i];
        }
        if (($not_in_set[$i] - $not_in_set[$i-1]) > 1) {
            $not_in_set_meta['mins'][] = $not_in_set[$i];
        }
    }
}

Output finale:

// The final variable which we'll dump the ranges not covered into:
$non_sets = array();

while(count($not_in_set_meta['mins']) > 0 && count($not_in_set_meta['maxes'])) {
    $non_sets[] = array(array_shift($not_in_set_meta['mins']), 
                        array_shift($not_in_set_meta['maxes']));
}
// print it out:
print var_export($non_sets);

Risultato:

array (
  0 => 
  array (
    0 => 1101,
    1 => 1499,
  ),
  1 => 
  array (
    0 => 1601,
    1 => 1899,
  ),
)

?>