[Go] Insertion sort / merge with comments
Very Go-unfriendly problem. We don\'t have TreeMaps or sets..\n\nKeep a slice of intervals. Binary search for the relevant interval to consider for [left, right
Very Go-unfriendly problem. We don\'t have TreeMaps or sets..\n\nKeep a slice of intervals. Binary search for the relevant interval to consider for [left, right].\n\nThen consider all cases. If necessary, merge several intervals into a single one using `copy`.\n\n```go\ntype CountIntervals struct {\n\tintervals []interval\n\tcount     int\n}\n\ntype interval struct {\n\tstart, end int\n}\n\nfunc Constructor() CountIntervals {\n\tc := CountIntervals{\n\t\tintervals: make([]interval, 0, 100),\n\t}\n\t// Add sentinel values to make indexing easier\n\tc.intervals = append(c.intervals,\n\t\tinterval{-100, -99},\n\t\tinterval{1e9 + 1, 1e9 + 2},\n\t)\n\treturn c\n}\n\nfunc (this *CountIntervals) Add(left int, right int) {\n\tright++ // easier to work with open-ended intervals\n\n\t// Binary search for first and second interval.\n\t// These may be the same interval\n\tfirst := sort.Search(len(this.intervals), func(i int) bool {\n\t\treturn left <= this.intervals[i].end\n\t})\n\tsecond := sort.Search(len(this.intervals), func(i int) bool {\n\t\treturn this.intervals[i].start > right\n\t}) - 1\n\n\t// In the following if-statements, I will use the notation <left> <right>\n\t// [ ), where [ ) refers to an interval.\n\t//\n\t// For example: "<left> [ )" means that the left value is smaller than the\n\t// start value of an interval.\n\n\tif right < this.intervals[first].start {\n\t\t// <left> <right> [ )\n\t\t// Create a new interval and return.\n\t\tthis.intervals = append(this.intervals, interval{})\n\t\tcopy(this.intervals[first+1:], this.intervals[first:])\n\t\tthis.intervals[first] = interval{left, right}\n\t\tthis.count += right - left\n\t\treturn\n\t} else if right > this.intervals[second].end {\n\t\t// We know that <left> is <= the right boundary of the first interval.\n\t\t// So [ ) <left> <right> cannot happen.\n\t\t//\n\t\t// It\'s safe to assume that we should update the right-boundary of the\n\t\t// second interval, i.e. we have\n\t\t// [ ) <right>\n\t\tthis.count += right - this.intervals[second].end\n\t\tthis.intervals[second].end = right\n\t} else {\n\t\t// right is inside the second interval - no need to update any intervals\n\t\t// (however, we might need to merge later on).\n\t\t// [ <right> )\n\t}\n\n\tif left < this.intervals[first].start {\n\t\t// We know that <right> to the right of the start boundary of the first\n\t\t// interval. So we can safely assume that the start boundary of the first\n\t\t// interval should be updated.\n\t\t//\n\t\t// Example cases:\n\t\t// <left> [ <right> ) or <left> [ ) <right>, etc\n\t\tthis.count += this.intervals[first].start - left\n\t\tthis.intervals[first].start = left\n\t} else {\n\t\t// <left> is inside the interval - no need to update\n\t}\n\n\t// If first != second, merge intervals. These actions will do nothing when\n\t// start == end so no need to check.\n\tfor j := first + 1; j <= second; j++ {\n\t\tthis.count += this.intervals[j].start - this.intervals[j-1].end\n\t}\n\tthis.intervals[second].start = this.intervals[first].start\n\tcopy(this.intervals[first:], this.intervals[second:])\n\tthis.intervals = this.intervals[:len(this.intervals)-(second-first)]\n}\n\nfunc (this *CountIntervals) Count() int {\n\treturn this.count\n}\n```
['Go']