package main

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
func insert(intervals []Interval, newInterval Interval) (in []Interval) {
	n := len(intervals)
	if n == 0 {
		return append(in, newInterval)
	}
	beg := search(intervals, 0, n-1, newInterval.Start)
	end := search(intervals, beg, n-1, newInterval.End)
	l, r := newInterval.Start, newInterval.End
	if beg > n-1 { // It's trival, but also very important
		in = intervals
	} else if l < intervals[beg].Start {
		in = append(in, intervals[:beg]...) // And, copy instead of reference
	} else if l > intervals[beg].End {
		in = append(in, intervals[:beg+1]...)
	} else {
		l = intervals[beg].Start
		in = append(in, intervals[:beg]...)
	}
	if end > n-1 {
		in = append(in, Interval{l, r})
	} else if r < intervals[end].Start {
		in = append(in, Interval{l, r})
		in = append(in, intervals[end:]...)
	} else if r > intervals[end].End {
		in = append(in, Interval{l, r})
		if end != n-1 {
			in = append(in, intervals[end+1:]...)
		}
	} else {
		r = intervals[end].End
		in = append(in, Interval{l, r})
		if end != n-1 {
			in = append(in, intervals[end+1:]...)
		}
	}
	return
}

func search(in []Interval, beg, end, val int) int { // Binary search in intervals
	for beg <= end {
		mid := (beg + end) / 2
		if val > in[mid].End {
			beg = mid + 1
		} else if val < in[mid].Start {
			end = mid - 1
		} else {
			return mid
		}
	}
	return beg
}

// func main() {
// 	in := []Interval{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}
// 	ans := insert(in, Interval{4, 8})
// 	fmt.Println(ans)
// 	in = []Interval{{1, 5}}
// 	ans = insert(in, Interval{6, 8})
// 	fmt.Println(ans)
// 	in = []Interval{}
// 	ans = insert(in, Interval{2, 7})
// 	fmt.Println(ans)
// 	in = []Interval{{1, 5}}
// 	ans = insert(in, Interval{0, 0})
// 	fmt.Println(ans)
// }