This is where things actually are different. Note that I insert the new intervals using the insert(it, ...) syntax. This inserts the new value *before* the iterator. Thus I insert left, then right. So the original list has
    ... <-> it <-> ...
and after the insertions it looks like
    ... <-> left <-> right <-> it <-> ...
We then remove it and left/right will be in the correct spot in the list.