时报设定联盟和消除

Question

我有事件的列表，开始和结束时间，有些东西像下面这样：

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的实现是首选，但也欢迎任何其他实现。

Answer 1

我不认为应该有一个算法，会更好，你的自定义的，因为这样会更容易调整它，当需求会改变。

这里应该是可以理解的任何开发人员都一个工作版本：

<?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) 
    } 
}