I'd say this problem is slightly trickier than it looks at first.

An elegant way to do this is to define a closed algebra on intervals with the operations union, complement and intersection: you can formulate your problem as intersection(big_timeframe, complement(union(taken_timeframes))).

This can be done in an optimal way in a functional language using scanline-type algorithms on lists, or slightly less optimally and more clearly using the scanline idea and an intermediate datastructure that partitions the intervals into disjoint subintervals pointing to their containing parent intervals. I'd opt for the latter.

You can build these operations easily using the following method:

Notation: {A, B} is a tuple representing an interval, A <= B. {} means tuple, [] means list.

1) Decompose intervals into [{Endpoint, Parent_interval}, ...]. Eg. the interval {A, B} is decomposed into the list [{A, {A, B}}, {B, {A, B}}].

2) Sort this based on Endpoint.

3) Use these endpoints to build disjoint subintervals which know their containing parent intervals, your datastructure is [{Subinterval, Parent_intervals_set}, ...]. 2) and 3) is basically a 1-d scanline algorithm.

4) Find the subintervals that satisfy your predicate (union, intersection, complement). For example, union simply means find subintervals whose Parent_interval_set is nonempty. The filter hof is useful for expressing these.

5) Merge contiguous subintervals.

6) ???

7) Profit.


This can be optimized by writing union, intersection and complement directly without going through
the subintervals indirection, but that's wordier and trickier.

You don't have to use an if to return true or false from a boolean espression. You can directly use the boolean expression (negating it in case of need). So

let containedIn a b = if b.start <= a.start && endOf b >= endOf a then true else false

can be simply written as

let containedIn a b = b.start <= a.start && endOf b >= endOf a

and so on. This is valid in every language, not just F# (which I actually don't know very well). More trickier is the collidesWith function which may become

let collidesWith a b = (a.start >= b.start && a.start < endOf || (endOf a > b.start && endOf a < endOf

You're right, I was less than clear. The nudge I expected to give was to look at sweepline algorithms but I wrote scanline instead. Sorry.

I don't know F#, but that algorithm looks quadratic (it seems you're applying min operations to the list for every interval).

Here's another stab at an explanation with accompanying Haskell code.

Suppose you have a list of intervals that contains the occupied intervals AND the interval representing the timeframe.

You can partition the initial, overlapping, set of intervals into a set of disjoint intervals. If these disjoint intervals keep track of how many parent intervals overlap them, you can easily discard those with a > 1 overlap; the remaining intervals are free. This generalises to other interesting interval operations if you keep track of more than number of overlapping parents: this is where I was coming from.

You can accomplish this in O(nlogn) time or O(n) time if you get to use a non-comparison sort like radix sort. HOW you accomplish this is by first decomposing intervals into their endpoints, sorting them, and sweeping over these to generate subintervals and overlap counts.

Once you've done this, all that remains is to filter out those intervals with intersection counts > 1. The same approach works for many other interval-related problems.


import Data.List

data Interval a = In a a Int deriving ( Show )
data Point a = Pt a Int deriving ( Show )

decompose = concat . map (\(In a b _) -> [Pt a 1, Pt b (-1)])

disjoint [] = []
disjoint (Pt a e:xs) = disjoint_h e a xs

disjoint_h _ _ [] = []
disjoint_h accum a (Pt b e:rest) = In a b accum: disjoint_h (accum + e) b rest

cmp (Pt a _) (Pt b _) = compare a b
prune_empty_intervals = filter (\(In a b _) -> a /=

build_disjoint :: [Interval Int] -> [Interval Int]
build_disjoint = prune_empty_intervals . disjoint . (sortBy cmp) . decompose

to_internal = map (\(a, -> In a b 1)
from_internal = map (\(In a b accum) -> (a, )

find_free = from_internal . find_free_h . to_internal
find_free_h intervals = filter (\(In _ _ accum) -> accum == 1) (build_disjoint intervals)


So, let's say we have a timeframe of 1 to 10 and a few occupied intervals:


*Main> find_free [(1, 10), (1,2), (3, 6), (7, 9)]
[(2,3),(6,7),(9,10)]
*Main>


edit: removed comments, highlighting makes the code with them harder to read

Heh, the forum software mysteriously decided to uppercase some variable names in the code section above, breaking stuff.