Times Sets Union and Elimination

Question

I have a list of events with starting and ending time, some thing like the following:

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

In the listing above, start is given ordered ascending. I need the following:

1. Items 2&3 should be eliminated because it is completely a sub set of item 1
2. Items 1&4 AND 5&6 should be unionized as two items to be Start at 1 and End at 11, Start at 12 and End at 25.

So finally I should have two items only instead of 6. I could not able to figure out any algorithm that handles this problem.

I have tried looping through the list's items using for something like the following:

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

My main question is: Is there any known algorithm that solves this problem? ,PHP implementation is preferred, but any other implementation is welcomed too.

Answer 1

I don't think there should be an algorithm that would be better that your custom one, because that's way it would be easier to tweak it when requirements would change.

Here is a working version which should be understandable by any developer:

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

I don't like naming and confusion that some functions return boolean, one returns integer and two others return arrays, but as an algorithm draft to illustrate the idea I think it's acceptable.

Output:

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