Вычисления диапазонов чисел в PHP

Question

и прежде всего, спасибо, что нашли время прочитать мой вопрос.

Я пытаюсь написать сценарий, и я столкнулся с проблемой, которую, как мне кажется, трудно решить.Я работаю с парой чисел (например, 1000 и 2000), и у меня есть массив пар чисел:

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

Что я пытаюсь найти, так это как получить диапазоны, не охватываемые парами чисел, между 1000 и 2000.В этом примере 1000-1100 покрывается массивом (800, 1100), 1500-1600 покрывается массивом (1500, 1600), а 1900-2000 покрывается массивом (1900, 2100), что оставляет мне 1101-1499 и 1599-1899 для покрытия.Надеюсь, я выражаюсь достаточно ясно.

Что мне интересно, так это как бы я заставил PHP возвращать мне массив диапазонов, не охватываемых переменной $pairs.В этом примере это вернет:

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

У вас есть какие-нибудь идеи, как лучше всего это сделать?

Заранее благодарю вас.

Answer 1

Ну, во-первых, вы должны определить проблему:

<Ол>

Сортированы ли пары?

Пересекаются ли пары?

Вы хотите найти пропущенные диапазоны для определенного диапазона (похоже, это так)?

Если пары не отсортированы, сначала отсортируйте их:

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;
  }
}

Если разрешены перекрывающиеся диапазоны, преобразуйте список пар в неперекрывающийся набор. Вот одно предложение о том, как это сделать:

$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;

Теперь не должно быть перекрывающихся пар, поэтому проблема становится немного проще, поскольку у вас также есть отсортированный массив.

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;
}

Надеюсь, это поможет.

Answer 2

Я бы сделал что-то подобное:

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

Это всего лишь идея, но вот в чем суть: Предположим, у вас есть большой сегмент (от 1000 до 2000) и маленький. Вы хотите получить все сегменты большого, которые не покрыты маленьким. Представь, что у тебя есть ручка!

Инициируйте начало. Выполните итерацию на каждом «маленьком сегменте» у тебя есть. Если после (строго) начала есть «дыра», поэтому вы должны запомнить, чем от начала до начала текущего сегмента.

Надеюсь, это поможет и что это правильно!

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];

Найдите разницу в массиве

// 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);

Метаданные о наборах мы будем использовать позже:

// 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];
        }
    }
}

Конечный результат:

// 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);

Результат:

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

?>