Finding overlap among groups of date ranges

Imagine you have two groups of date ranges and you want to determine whether they overlap.

Nah, let's make it harder. Imagine you have two groups of include date ranges and two groups of exclude date ranges. Your task is to determine, whether there's a date that is present in both include groups and not present in exclude groups. How to do that?

Gotta warn you that in my case it was a config validation. Which means it's performed seldom and range groups are quite small. In this case algorithm simplicity was much more important than speed.

The algorithm works in 2 stages: convert ranges to array of events and follow these events to update the state.

Stage 1: Convert ranges to array of events

We need an array of events grouped by date. Each event contains information like "include group 1 range starts" or "exclude group 2 range ends".

function addGroupToEvents(array $events, array $ranges, string $key): array
{
    foreach ($ranges as $range) {
        $startDate = $range['start'];
        $endDate = $range['end'];

        // Add defaults
        $events += [
            $startDate => ['starts' => [], 'ends' => []],
            $endDate => ['starts' => [], 'ends' => []],
        ];

        // Add events
        $events[$startDate]['starts'][] = $key;
        $events[$endDate]['ends'][] = $key;
    }

    return $events;
}

$events = [];
addGroupToEvents($events, $includeGroup1, 'include1');
addGroupToEvents($events, $includeGroup2, 'include2');
addGroupToEvents($events, $excludeGroup1, 'exclude1');
addGroupToEvents($events, $excludeGroup2, 'exclude2');
ksort($events);

/*
$events = [
    '2018-01-01' => [
        'starts' => ['include1'],
        'ends' => [],
    ],
    '2018-01-10' => [
        'starts' => ['include2'],
        'ends' => ['include1'],
    ],
    ...
];
*/

Date format 'yyyy-mm-dd' allows you to sort dates as strings — it will just work.

Stage 2: Follow events to update the state

Now we track state of each range group and update it date by date. After each step we can check if state meets expected condition.

$state = [
    'include1' => 0,
    'include2' => 0,
    'exclude1' => 0,
    'exclude2' => 0,
];
foreach ($events as $date => $eventGroup) {
    foreach ($eventGroup['starts'] as $key) {
        $state[$key]++;
    }

    $isOverlapping =
        $state['include1'] > 0 &&
        $state['include2'] > 0 &&
        $state['exclude1'] == 0 &&
        $state['exclude2'] == 0;
    if ($isOverlapping) {
        // $date is the first date of ranges overlapping
        return true;
    }

    foreach ($eventGroup['ends'] as $key) {
        $state[$key]--;
    }
}

return false; // No overlap

Two things to notice:

  • We're processing "ends" after checking state. The easiest way to understand why is to imagine a one-day range.
  • We're storing state in integer instead of booleans for case of overlapping in same range group.

Summary

It's the simplest way I could solve this task. If you know better one — describe it to me in comments.

Tags: ,

Comments