StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAlgorithm to validate a list of intervals
text
Body
copied!<p>Given a list of start / end datetime values I need to validate three things:</p> <ol> <li>for each interval, the start time is before the end time</li> <li>no overlap exists between list elements, each start / end span must represent a discrete interval in the overall list</li> <li>there can be no gaps in the series, from the earliest start to the latest end there must be continuous coverage.</li> </ol> <p>So, given:</p> <pre><code>( (1970-01-01, 1970-12-31), (1971-01-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) ) </code></pre> <p>A success result is given.</p> <p>Given</p> <pre><code>( (1970-12-31, 1970-01-01), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) ) </code></pre> <p>A message stating that the start date comes after the end date in the first element is provided.</p> <p>Given</p> <pre><code>( (1970-01-01, 1970-12-31), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) ) </code></pre> <p>A message stating that overlap exists between the first and second elements is provided.</p> <p>Given</p> <pre><code>( (1970-01-01, 1970-12-31), (1971-10-01, 1971-12-31), (1973-01-01, 1973-12-31), (1974-01-01, 1974-12-31) ) </code></pre> <p>A message stating that a gap exists between second and third elements is provided.</p> <p>The first requirement is dirt simple, the question is how can it best be rolled into a broader validation.</p> <p>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? <a href="https://stackoverflow.com/questions/325933/determine-whether-two-date-ranges-overlap">Determine Whether Two Date Ranges Overlap</a></p> <p>This article - <a href="https://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals">search for interval overlap in list of intervals?</a> - seems to better address the second requirement, and the first can be rolled into the population of the interval tree.</p> <p>So that leaves the third requirement. Is it possible to determine gaps in the overall interval using the interval tree?</p> <p>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...</p> <p>Thanks!</p> <p>r/Steve</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload