Таймс устанавливает союз и ликвидацию

У меня есть список событий с начальным и конечным временем, что-то вроде следующего:

Id     Start      End
1      1           10
2      4           9
3      5           8
4      6           11
5      12          20
6      18          25

В списке выше, Начните дается в порядке возрастания. Мне нужно следующее:

  1. Предметы 2&3 следует исключить, поскольку это полностью подмножество пункта 1
  2. Предметы 1&4 И 5&6 должны быть объединены в два элемента, начиная с 1 и заканчивая в 11, начиная с 12 и заканчивая в 25.

Итак, наконец, у меня должно быть только два элемента вместо 6. Я не смог найти ни одного алгоритма, который бы решал эту проблему.

Я попытался перебирать элементы списка, используя что-то вроде следующего:

$startArr = [];
$endArr   = [];
for ($i=0; $i<count($arr); $i++){
if (isset($arr[$i+1])){
// check the next item end
if ($arr[$i]['end'] > $arr[$i+1]['end']){
$startArr[] = $arr[$i]['start'];
$endArr[] = $arr[$i]['end'];
// here is the problem, what could I can do
// for item 1 and 3
}
}
}

Мой главный вопрос: есть ли известный алгоритм, который решает эту проблему? ,Реализация PHP предпочтительнее, но приветствуется и любая другая реализация.

3

Решение

Я не думаю, что должен быть алгоритм, который был бы лучше, чем ваш, потому что таким образом было бы легче настроить его, когда требования изменятся.

Вот рабочая версия, которая должна быть понятна любому разработчику:

<?php

$input = [
['id' => 1, 'start' => 1,  'end' => 10 ],
['id' => 2, 'start' => 4,  'end' => 9  ],
['id' => 3, 'start' => 5,  'end' => 8  ],
['id' => 4, 'start' => 6,  'end' => 11 ],
['id' => 5, 'start' => 12, 'end' => 20 ],
['id' => 6, 'start' => 18, 'end' => 25 ],
];

$output = [];
$output[] = $input[0];

foreach ($input as $event) {
if (isEventEqual($event, $output) or isEventFullyInside($event, $output)) {
continue;
} elseif (isEventFullyOutside($event, $output)) {
$output[] = $event;
} elseif (isEventFullyWrap($event, $output)) {
$output[isEventFullyWrap($event, $output)] = $event;
} elseif (wasEventStartedBeforeAndFinishedInside($event, $output)) {
list($indexOfEventToUpdate, $updatedEvent) = wasEventStartedBeforeAndFinishedInside($event, $output);
$output[$indexOfEventToUpdate] = $updatedEvent;
} elseif (wasEventStartedInsideAndFinishedAfter($event, $output)) {
list($indexOfEventToUpdate, $updatedEvent) = wasEventStartedInsideAndFinishedAfter($event, $output);
$output[$indexOfEventToUpdate] = $updatedEvent;
}
}

var_dump($output);

function isEventEqual($event, $output) {
$isEventEqual = false;
foreach($output as $checked) {
if ($checked['start'] === $event['start'] and $checked['end'] === $event['end']) {
$isEventEqual = true;
}
}
return $isEventEqual;
}

function isEventFullyOutside($event, $output) {
$isEventFullyOutside = false;
foreach($output as $checked) {
$isEventFullyBefore = $event['end']   < $checked['start'];
$isEventFullyAfter  = $event['start'] > $checked['end'];
$isEventFullyOutside = ($isEventFullyBefore or $isEventFullyAfter);
}
return $isEventFullyOutside;
}

function isEventFullyInside($event, $output) {
$isEventFullyInside = false;
foreach($output as $checked) {
$isEventStartedAfter   = $event['start'] > $checked['start'];
$isEventFinishedBefore = $event['end']   < $checked['end'];
$isEventFullyInside = ($isEventStartedAfter and $isEventFinishedBefore);
}
return $isEventFullyInside;
}

function isEventFullyWrap($event, $output) {
foreach($output as $index => $checked) {
if ($checked['start'] > $event['start'] and $checked['end'] < $event['end']) {
return $index;
}
}
return false;
}

function wasEventStartedBeforeAndFinishedInside($event, $output) {
foreach($output as $index => $checked) {
if ($checked['start'] > $event['start'] and $checked['start'] > $event['end']  and $checked['end'] > $event['end']) {
$checked['start'] = $event['start'];
return [$index, $checked];
}
}
return false;
}

function wasEventStartedInsideAndFinishedAfter($event, $output) {
foreach($output as $index => $checked) {
if ($checked['start'] < $event['start'] and $checked['end'] > $event['start'] and $checked['end'] < $event['end']) {
$checked['end'] = $event['end'];
return [$index, $checked];
}
}
return false;
}

Мне не нравится называть и путать, что некоторые функции возвращают логическое значение, одна возвращает целое число, а две другие возвращают массивы, но в качестве черновика алгоритма, чтобы проиллюстрировать идею, я думаю, что это приемлемо.

Выход:

array(2) {
[0] =>
array(3) {
'id' =>    int(1)
'start' => int(1)
'end' =>   int(11)
}
[1] =>
array(3) {
'id' =>    int(5)
'start' => int(12)
'end' =>   int(25)
}
}
2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector