Golang binary search


  • 0
    R
    
    type ByLength []Interval
    
    func (s ByLength) Len() int {
        return len(s)
    }
    func (s ByLength) Swap(i, j int) {
        s[i], s[j] = s[j], s[i]
    }
    func (s ByLength) Less(i, j int) bool {
        return s[i].Start < s[j].Start
    } 
     
     
    func findRightInterval(intervals []Interval) []int {
        original := make(map[int]int)
        for i, _ := range intervals {
            original[intervals[i].Start] = i
        }
        sort.Sort(ByLength(intervals))
        
        ans := make(map[int]int)
        
        for k, v := range intervals {
            lo := 0
            hi := len(intervals)-1
            mid := 0
            for lo < hi {
                mid = lo + (hi - lo) / 2
                if intervals[mid].Start >= v.End {
                    hi = mid
                } else {
                    lo = mid + 1
                }
            }
            if intervals[lo].Start >= v.End && lo != k {
                ans[original[intervals[k].Start]] = original[intervals[lo].Start] 
            } else {
                ans[original[intervals[k].Start]] = -1
            }
        }        
        res := make([]int, 0)      
        for i, _ := range intervals {
            res = append(res, ans[i])
        }
        
        return res
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.