Расчет диапазонов чисел в 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

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

1. сортируют пары?
2. Не перекрываются ли пары?
3. Вы хотите найти недостающие диапазоны для определенного диапазона (похоже, это так)?

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

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, 
), 
) 

?>