golang solution


  • 0
    C
    import (
        "math"
        "container/heap"
    )
    
    type PQ [][]int
    
    func (pq *PQ) Len() int {
        return len(*pq)
    }
    
    func (pq *PQ) Swap(i, j int) {
        (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
    }
    
    func (pq *PQ) Less(i,j int) bool {
        return (*pq)[i][0] < (*pq)[j][0]
    }
    
    func (pq *PQ) Push(x interface{}) {
        *pq = append(*pq, x.([]int))
    }
    
    func (pq *PQ) Pop() interface{} {
        v := (*pq)[pq.Len()-1]
        *pq = (*pq)[:pq.Len()-1]
        return v
    }
    
    func smallestRange(nums [][]int) []int {
        res := make([]int, 2)
        res[0] = math.MinInt32
        res[1] = math.MaxInt32
        max := math.MinInt32
        pq := make(PQ, len(nums))
        for i := range nums {
            if len(nums[i]) == 0 {
                return res
            }
            pq[i] = nums[i]
            if nums[i][0] > max {
                max = nums[i][0]
            }
        }
        heap.Init(&pq)
        for {
            curr := heap.Pop(&pq).([]int)
            if max - curr[0] < res[1] - res[0] {
                res[0] = curr[0]
                res[1] = max
            }
             
            if len(curr) == 1 {
                return res 
            }
            heap.Push(&pq, curr[1:])
            if curr[1] > max {
                max = curr[1]
            }
        }   
    }
    

Log in to reply
 

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