Layered intervals algorithm

This page describes an algorithm created to calculate a final set of intervals from a set of layered intervals linearly (i.e., from left to right).

The above images are examples of composed intervals (the lines are the paths taken by the algorithm).

As you can see, the main obstacle in calculating such composed intervals is accounting for obstructions in more important (i.e., higher priority) layers.

This is the simplest method to perform this computation in a linear way I could come up with.

For a tree approach, see [1].

Pseudocode

    from first to last node, ordered by position first and ascending lane second:
    if not closing:
        if not open in any higher lane:
            if final opened:
                close final.
            open final.
        open in this lane.
    if closing:
        closed in this lane.
        if final opened:
            if not open in any higher lane:
                close final.
    if not final opened:
        if at last lane of position, except for the last position:
            if open in any other lane:
                open final.

Implementations

With tests.

• C#

1. Interval tree (Wikipedia)