Algorithm to validate a list of intervals

Question

Given a list of start / end datetime values I need to validate three things:

for each interval, the start time is before the end time
no overlap exists between list elements, each start / end span must represent a discrete interval in the overall list
there can be no gaps in the series, from the earliest start to the latest end there must be continuous coverage.

So, given:

( (1970-01-01, 1970-12-31), (1971-01-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) )

A success result is given.

Given

( (1970-12-31, 1970-01-01), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) )

A message stating that the start date comes after the end date in the first element is provided.

Given

( (1970-01-01, 1970-12-31), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) )

A message stating that overlap exists between the first and second elements is provided.

Given

( (1970-01-01, 1970-12-31), (1971-10-01, 1971-12-31), (1973-01-01, 1973-12-31), (1974-01-01, 1974-12-31) )

A message stating that a gap exists between second and third elements is provided.

The first requirement is dirt simple, the question is how can it best be rolled into a broader validation.

The second requirement is somewhat met by the article below, but since it works for only a pair of intervals, I would still realize O(n^2) as each element would need to be compared against every other element, correct? Determine Whether Two Date Ranges Overlap

This article - search for interval overlap in list of intervals? - seems to better address the second requirement, and the first can be rolled into the population of the interval tree.

So that leaves the third requirement. Is it possible to determine gaps in the overall interval using the interval tree?

I'll mention that this is in Javascript, node.js. However, it would be interesting to work this out in Haskell or another functional language...

Thanks!

r/Steve

since all 3 conditions are easily solved using *real* intervals, why don't you "translate" these date ranges to integer intervals, run the 3 algorithms and then translate it back to dates. it's easy to find a function(date)->Integer which will be 1-1 and on (hence reversible). — Nir Alfasi, Jun 28 '12 at 23:16

Ioannis Karadimas · Accepted Answer · 2012-06-29T02:35:31.137

This code provides a solution, although I am assuming the following:

You don't mind the list being sorted. It greatly reduces the number of comparisons to do.
Your comparison between dates is in day level, given your examples. If not, you 'll probably need to change the strToDate function, as well as the adjustment variable.

The idea was taken from @alfasin.

var data = [
    ['1970-01-01', '1970-12-31'], 
    ['1971-01-01', '1971-12-31'], 
    ['1972-01-01', '1972-12-31'], 
    ['1973-01-01', '1973-12-31']
];

// comparison is in day level, adjust otherwise.
var adjustment = 1000 * 60 * 60 * 24;

var parsedData = [];
for(var idx = 0; idx < data.length; idx++) {
    var thisItem = data[idx];

    var thisParsedItem = [
        Math.floor(strToDate(thisItem[0]).getTime() / adjustment), 
        Math.floor(strToDate(thisItem[1]).getTime() / adjustment),
        // adding original items here, since I plan to sort the list.
        thisItem[0],
        thisItem[1]
    ];

    parsedData.push(thisParsedItem);
}

parsedData = parsedData.sort(function (itemA, itemB) {
    return itemA[0] - itemB[0];
});


var errorLocation = -1, overlap = false, gap = false, endBeforeStart = false;
for(var idx = 0; idx < parsedData.length - 1; idx++) {
    // start before end.
    if (parsedData[idx][0] > parsedData[idx][1]) {
        errorLocation = idx;
        endBeforeStart = true;
        break;
    }

    var d = parsedData[idx + 1][0] - parsedData[idx][1];

    // gap.
    if (d > 1) {
        errorLocation = idx + 1;
        gap = true;
        break;
    }

    // overlap.
    if (d < 1) {
        errorLocation = idx + 1;
        overlap = true;
        break;
    }
}

if (errorLocation > -1) {
    if (gap) { console.log("You have a gap at: " + errorLocation); }
    if (overlap) { console.log("You have an overlap at: " + errorLocation); }
    if (endBeforeStart) { console.log("End before start at: " 
                                  + errorLocation); }
}

function strToDate(input) {
    var parts = input.split('-');
    return new Date(
            parseInt(parts[0]), 
            parseInt(parts[1]), 
            parseInt(parts[2]));
}

Works. I have made some tweaks to support the more involved data structure in our solution, and the algorithm now report multiple errors in a list. The only condition where this is not possible is the case where the end date is prior to the start date. When that case is encountered the algorithm exits immediately. I simply removed the break statements from the gap and overlap cases; and added an array that is populated with the messages in these cases and returned from the function. Thanks muchly, your input and efforts are appreciated! — Steve Wagner, Jun 29 '12 at 18:11

score 0 · Answer 2 · edited May 23 '17 at 12:18

0

Parse the date first using something like datetime.datetime.strptime in python and convert date to milliseconds and do simple checks.

Get current time in milliseconds in Python?

edited May 23 '17 at 12:18

Community

1
1

answered Jun 29 '12 at 01:25

specialscope

4,188
3
24
22

score 0 · Answer 3 · answered Jun 29 '12 at 01:31

Without providing a full working example, you could do the following:

Sort the list by start date (in the sorting function you could also validate if start < end)
Iterate through the list and make sure that either:
1. item is the first item of the list
2. start date is one more than the previous stop date

I suppose this doesn't really bring down the order of the function though (N x N log N), unless it was already sorted and you could skip step 1.

Algorithm to validate a list of intervals

3 Answers3