leetcode-go/leetcode/medium/435.non-overlapping-intervals.go

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
func eraseOverlapIntervals(intervals []Interval) (res int) {
	sort.Sort(inters(intervals))
	fast, slow, n := 1, 0, len(intervals)
	for ; fast < n; fast++ { // Greedy
		if intervals[fast].Start < intervals[slow].End { // If overlaps,
			if intervals[fast].End < intervals[slow].End { // Choose the interval that ends earlier
				slow = fast
			}
			res++
		} else {
			slow = fast
		}
	}
	return
}

type inters []Interval

func (is inters) Len() int           { return len(is) }
func (is inters) Less(i, j int) bool { return is[i].Start < is[j].Start }
func (is inters) Swap(i, j int)      { is[i], is[j] = is[j], is[i] }