I have a set of non-overlapping, non-adjacent intervals, eg. [{10,15}, {30,35}, {20,25}]. They are not sorted, but I can sort them if necessary.

Now I am given some new interval, eg. {5,32} and want to generate a new set of intervals describing the difference: the ranges covered by this new interval that aren't in the set. In this example the answer would be: [{5,9}, {16,19}, {26,29}].

What's a fast algorithm for calculating this? Note that the set will typically have 1, sometimes 2, rarely 3 or more items in it, so I want to optimise for this case.

For context, here's the code for initially creating the set from an input stream of start+end data, where I merge as I go:

```
type Interval struct {
    start int
    end   int
}

func (i *Interval) OverlapsOrAdjacent(j Interval) bool {
    return i.end+1 >= j.start && j.end+1 >= i.start
}

func (i *Interval) Merge(j Interval) bool {
    if !i.OverlapsOrAdjacent(j) {
        return false
    }
    if j.start < i.start {
        i.start = j.start
    }
    if j.end > i.end {
        i.end = j.end
    }
    return true
}

type Intervals []Interval

func (ivs Intervals) Len() int           { return len(ivs) }
func (ivs Intervals) Swap(i, j int)      { ivs[i], ivs[j] = ivs[j], ivs[i] }
func (ivs Intervals) Less(i, j int) bool { return ivs[i].start < ivs[j].start }

func (ivs Intervals) Merge(iv Interval) Intervals {
    ivs = append(ivs, iv)
    merged := make(Intervals, 0, len(ivs))
    for _, iv := range ivs {
        for i := 0; i < len(merged); {
            if iv.Merge(merged[i]) {
                merged = append(merged[:i], merged[i+1:]...)
            } else {
                i++
            }
        }
        merged = append(merged, iv)
    }
    return merged
}

func (ivs Intervals) MergeUsingSort(iv Interval) Intervals {
    ivs = append(ivs, iv)
    sort.Sort(ivs)
    merged := make(Intervals, 0, len(ivs))
    merged = append(merged, ivs[0])
    for i := 1; i < len(ivs); i++ {
        last := len(merged) - 1
        if !merged[last].Merge(ivs[i]) {
            merged = append(merged, ivs[i])
        }
    }
    return merged
}

func (ivs Intervals) Difference(iv Interval) Intervals {
    // ???
    return ivs
}

func main() {
    var ivs Intervals
    for _, input := range inputsFromSomewhere { // in reality, I don't have all these inputs at once, they come in one at a time
        iv := Interval{input.start, input.end}
        diffs := ivs.Difference(iv) // not yet implemented...
        // do something with diffs
        ivs = ivs.Merge(iv)
    }
}

```

I find that the above Intervals.Merge() is 2x faster than MergeUsingSort(), so I wonder if there's also a simple non-sorting way of answering my question.