How to cut sections from a number and get the remainder?

Question

PHP

Good afternoon, for example, there is a number 100,000 (one hundred thousand)
Let's say from 30 to 500 you need to cut
Next, cut from 1200 to 3700
And cut somewhere else ...
Thus, only free numbers should remain in the form of an array from and to, such as
array(
1 => [1, 30], 2 => [ 500
, 1200], 3 => [ 3700
, 100000] ,
) cut up to 35 And it turns out the total from 10 to 700. It turns out a certain function that takes the main number from and to from which we cut and an array with what needs to be cut and at the output you need to get an array of residuals.

Answer 1

I got cumbersome. Is there a more concise solution?

function cut(array $base, array $cuts = [])
{
    $parts = [];
    $cutParts = [];

    // сортируем вырезанные отрезки по началу
    usort($cuts, function (array $a, array $b) {
        return $a[0] - $b[0];
    });

    // склеиваем вырезанные отрезки
    foreach ($cuts as $cut) {
        $i = count($cutParts)-1;
        if ($i === -1) { // первый отрезок
            $cutParts[] = [max($base[0], $cut[0]), min($base[1], $cut[1])];
        } else {
            if ($cut[0] > $cutParts[$i][1]) { // новый отрезок
                $cutParts[] = [max($base[0], $cut[0]), min($base[1], $cut[1])];
            } else { // склейка
                $cutParts[$i][1] = max($cutParts[$i][1], $cut[1]);
            }
        }
    }

    // считаем, что осталось
    if ($cutParts[0][0] === $base[0]) { // начинать надо не от начала
        if ($cutParts[0][1] === $base[1]) { // вырезано все
            return [];
        } else { // начинаем отсчет с конца первого отрезка
            $parts[0] = [$cutParts[0][1]];
            array_shift($cutParts);
        }
    } else { // начинаем отсчет от начала исходного отрезка
        $parts[0] = [$base[0]];
    }
    foreach ($cutParts as $i => $cutPart) {
        $parts[$i][1] = $cutPart[0];
        if ($cutPart[1] < $base[1]) {
            $parts[$i + 1] = [$cutPart[1]];
        } else { // отрезок покрывает конец исходного отрезка
            return $parts;
        }
    }
    $parts[count($parts) - 1][1] = $base[1];

    return $parts;
}

print_r(cut([1, 100000], ));
print_r(cut([1, 1000], ));

Answer 2

v3shin , Basically the same + array_reduce

<?php
function cut($num, $remove_intervals) {
  // sort remove intervals by first value
  usort($remove_intervals, function($a, $b){return $a[0] <=> $b[0];});

  // merge overlapped intervals
  $remove = array_reduce(
    $remove_intervals,
    function($res, $el) {
      $cnt = count($res)-1;
      if ($el[0] <= $res[$cnt][1]) {
        $res[$cnt][1] = max($el[1], $res[$cnt][1]);
      } else {
        $res[] = $el;
      }
      
      return $res;
    },
    [$remove_intervals[0]]
  );
  // build result array
  $result = array_reduce(
    $remove,
    function($res, $el) use ($num) {
      $cnt = count($res)-1;
      
      if ($el[0] < $res[$cnt][1]) {
        $res[$cnt][1] = $el[0];
        if ($el[1] < $num) {
          $res[] = [$el[1], $num];
        }
      }
      return $res;
    },
    
  );
  
  var_export($result);

  return $result;
}
print_r(cut(10000, ));
print_r(cut(10000, ));
print_r(cut(1000, ));

Share PHP code online

Answer 3

Sort the start and end points of all segments together, labeled with +1 or -1 depending on the side.
Next, you have all the points on the number line. Walk along them from left to right, counting how many segments are open now. If there are 0 segments open between two points, add a segment in the answer.
A handy trick is to shift the beginnings of the segments by 1 to the left so that the segment that cuts out the number 1 (1..1) is 1 long.
Imagine that you have 10,000 unit pieces on the number line, from 0 to 10,000 - these are your original numbers. If you want to cut the segment 5..7 (numbers 5, 6 and 7), then you need to cut the segment [4...7] on this line - from point 4 to point 7.
Plus, add the start and end points so that you do not process them separately, and then you need to return all the segments covered by exactly one cut segment and you do not need to separately analyze the case of the leftmost and rightmost pieces in the answer.
php I don't know, here you go in C++. Ask if something is not clear:

vector<pair<int, int>> CutOutSegments(int begin, int end, vector<pair<int, int>> segments)
  // Массив из пар чисел. Пустой массив, в который будем добавлять строки из 2 чисел.
  vector<pair<int, int>> events; 
  events.push_back({begin-1, 1});  // добавляем строку с числами begin и 1.
  events.push_back({end, -1});
  for (auto s: segments) {
     events.push_back({s.first-1, 1});  // s.first - начало отрезка.
     events.push_back({s.second, -1});  // s.second  - конец отрезка.
  }
  sort(events.begin(), events.end());
  int prev_pos = events[0].first;
  int count = 0;
  vector<pair<int, int>> result;
  for (auto e: events) { // e - строка массива events. e.first/second - 2 числа в ней.
    if (prev_pos < e.first && count == 1) {
      result.push_back(prev_pos + 1, e.first); // добавялем +1, что бы отрезок [0, 1] был выдан как одно число 1..1.
    }
    count += e.second;
    if (e.first == end) break;
  }
  return result;
}

Perhaps the last loop could be rewritten with reduce, but it is unlikely to be shorter or more readable.