func Union(is []Interval, m Interval) []Interval {
	n := len(is)
	if n == 0 {
		return []Interval{m}
	}
	if m.End < is[0].Start {
		return append([]Interval{m}, is...)
	}
	if is[n-1].End < m.Start {
		return append(is, m)
	}
	merged := make([]Interval, 0, n)
	i := 0
	for ; is[i].End < m.Start; i++ {
		merged = append(merged, is[i])
	}
	j := i
	for ; j+1 < n && is[j+1].Start <= m.End; j++ {
	}
	merged = append(merged, Interval{
		Start: min(m.Start, is[i].Start),
		End:   max(m.End, is[j].End),
	})
	for i := j + 1; i < n; i++ {
		merged = append(merged, is[i])
	}
	return merged
}
Union merges m into the disjoint intervals is.
package solution
type Interval struct {
	Start int
	End   int
}