leetcode-go/leetcode/medium/436.find-right-interval.go

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
func findRightInterval(intervals []Interval) []int {
	n := len(intervals)
	res, starts := make([]int, n), make([][]int, n)
	for i := 0; i < n; i++ {
		starts[i] = []int{intervals[i].Start, i}
	}
	sort.Sort(ints(starts))
	for i := 0; i < n; i++ {
		beg, end := 0, n-1
		for beg <= end {
			mid := beg + (end-beg)/2
			if starts[mid][0] < intervals[i].End {
				beg = mid + 1
			} else {
				end = mid - 1
			}
		}
		if beg == n {
			res[i] = -1
		} else {
			res[i] = starts[beg][1]
		}
	}
	return res
}

type ints [][]int

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