It is very difficult to describe the task that I need to solve, but I will try.

There is a time interval (main): suppose it is the beginning and end of the day, which by default is red.

There is an array (A) of short intervals of time, which are placed in this first interval. They may be green and red.

It is necessary to impose this array on the main gap and get another array (B) of the intervals, observing several rules:

  1. The gaps of the array must go in order, in contact, but not intersect.
  2. In the final array, the gaps should go in order from the smallest to the largest, must be in contact with their neighbors, and have no empty spaces. The first gap should start from the time of the beginning of the main gap, the last one should end with the time of the end of the main gap.
  3. The colors in array B should be alternated. That is, it is not permissible for two colors to be near. In this case, the gaps should be merged.
  4. The gaps of the array A have priority from the smallest to the largest. That is, each next gap overrides previous others.

For greater clarity, I decided to draw a diagram:

Diagram

Why I ask: maybe there are ready-made tools, libraries or optimal algorithms that will help me solve this problem. I do not want to write crutches and bicycles.

Why it is needed: red and green colors mean busy and free time. Colors marked for simplification.

Given: PHP. You can operate with anything: DateTimeInterface objects, League \ Period \ Period objects (which is also actively used in the project) or regular TimeStamp tags. I'll figure it out next what to do about it.

  • I think you need to write such custom logic yourself, it’s just not clear what the intended solution or library should look like - Maksym Prus
  • the task is not very difficult, it is more difficult than 80% of the questions published here to "alter the array", but you just need to create an algorithm on paper, and then transfer it to the code. You will not find the library, and it makes no sense, there’s a solution in 15 lines, probably - teran
  • My first solution so far is this: 1. Divide the main period into the smallest gaps, based on the input data of the array (A) 2. Find the color of each piece, passing upwards through array A and checking whether this point falls into the period. 3. Combine the same colors. Solution in the forehead, I will try - Vitaly Zaslavsky
  • I also decided, I decided to check whether I’ll fit in 15 lines: D - teran

1 answer 1

While the question was hanging, I decided to quickly write the solution myself.

First of all, I create the Item class with the basic functionality:

class Item { public function __construct($start, $end, $type); public function getStart(); public function getEnd(); public function getType(); }

I decided to call the next class Collection . He will deal with the processing periods:

 class Collection { /** * @param Item $main * @param Item[] $items */ public function __construct(Item $main, array $items); }

Inside the constructor, checks are made so that each item from $ items is inside $ main

 $main->getStart() <= $item->getStart() && $item->getEnd() <= $main->getEnd()

Then the $ main element is inserted at the beginning of the $ items array and saved.

For the operation of logic, it is not necessary to store the main element separately, but it is advisable to check that all elements are within the main period, so that there is no unexpected behavior.

The first thing to do: break the main period into small ones. That is to collect all the points of the beginnings and ends of all periods.

It is difficult to explain, but the implementation of this logic is as follows:

 /** * @return int[] */ public function getPeriodDots() { $dots = []; foreach ($this->items as $item) { /** @var Item $item */ $dots = array_filter($dots, function ($dot) use ($item) { $inPeriod = $item->getStart() <= $dot && $dot <= $item->getEnd(); return !$inPeriod; }); $dots[] = $item->getStart(); $dots[] = $item->getEnd(); } sort($dots); return $dots; }

array_filter needed in order to remove those points that are overridden by another period.

The intervals between points are new periods, the type of which must be determined.

To determine the type of period, it is enough to take the beginning of this period and go through the array of $ items from the bottom up in the search for the parent period to which it belongs. (Still hard to explain)

Here is the implementation of the search type:

 /** * @param int $dot * @return int */ public function getTypeForDot($dot) { /** @var Item[] $items */ $items = array_reverse($this->items); $return = $this->items[0]->getType(); foreach ($items as $item) { if ($item->getStart() <= $dot && $dot < $item->getEnd()) { $return = $item->getType(); break; } } return $return; }

PS In general, return could be done inside foreach, but PHPStorm swears that there is not enough return at the end. And if you just leave the stub return $this->items[0]->getType(); or return 0; then we can never test this line and achieve 100% code coverage test.

But creating a new array of periods with the specified types:

 /** * @param int[] $dots * @return Item[] */ public function getNewItems($dots) { $startDots = array_slice($dots, 0, -1); $endDots = array_slice($dots, 1); $newItems = []; foreach ($startDots as $i => $start) { $end = $endDots[$i]; $type = $this->getTypeForDot($start); $newItems[] = new Item($start, $end, $type); } return $newItems; }

As a result, we get an array of new elements that go in a row, do not overlap and do not create voids. But...

The problem remains when several types go in a row.

The idea is simple: go through the array and combine periods that are of the same type.

Here is my decision. I think you can do better. If you have ideas, suggest.

 /** * @param Item[] $items * @return Item[] */ public function optimizePeriods($items) { $newItems = []; $item = array_shift($items); $start = $item->getStart(); $end = $item->getEnd(); $type = $item->getType(); foreach ($items as $item) { if ($item->getType() === $type) { $end = $item->getEnd(); continue; } $newItems[] = new Item($start, $end, $type); $start = $item->getStart(); $end = $item->getEnd(); $type = $item->getType(); } $newItems[] = new Item($start, $end, $type); return $newItems; }

As a result, you just need to combine all that we have done into one single function:

 public function getOptimized() { $dots = $this->getPeriodDots(); $items = $this->getNewItems($dots); return $this->optimizePeriods($items); }

Which returns us an array of elements corresponding to our task.

The result was a neat solution, well tested, independent of the framework.

The complete solution with 100% code coverage is laid out in gist . I decided to hide the namespaces, but the essence does not change.

If it is claimed, I can make a separate library.