時報設定聯盟和消除

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