Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

2406. Divide Intervals Into Minimum Number of Groups

有一個intervals矩陣:intervals[i]=[left_i,right_i]

要把interval分成一/多個group

這樣在同一個group裡的interval不會有交錯

請回傳最小的group數量

思路:

就用minimun heap

minimun heap裡面放的是interval的右邊界

每次先去看heap裡最小的右邊界是不是大/等於intervals[i]的左邊界

是的話表示intervals[i]會跟已經存在的interval交錯

所以把intervals[i]的右邊界push進minimun heap

反之就把minimun heap裡最小的右邊界pop出來

並且放入intervals[i]的右邊界

最後看minimun heap裡面有幾個數字就是答案

golang code :

type Generic_heap[T any] struct {
        data []T
        less func(T, T) bool
}

func (this Generic_heap[T]) Len() int           { return len(this.data) }
func (this Generic_heap[T]) Swap(i, j int)      { this.data[i], this.data[j] =
 this.data[j], this.data[i] }
func (this Generic_heap[T]) Less(i, j int) bool { return this.less(this.data[i
], this.data[j]) }
func (this *Generic_heap[T]) Pop() interface{} {
        n := len((*this).data)
        res := (*this).data[n-1]
        (*this).data = (*this).data[:n-1]
        return res
}
func (this *Generic_heap[T]) Push(x interface{}) {
        (*this).data = append((*this).data, x.(T))
}

func minGroups(intervals [][]int) int {
    slices.SortFunc(intervals, func(i, j []int) int { return i[0] - j[0] })
        h := Generic_heap[int]{make([]int, 0), func(i1, i2 int) bool { return i1 < i2
 }}
        for _, val := range intervals {
                if h.Len() > 0 && h.data[0] >= val[0] {
                        heap.Push(&h, val[1])
                } else {
                        if h.Len() > 0 {
                                heap.Pop(&h)
                        }
                        heap.Push(&h, val[1])
                }
        }
        return h.Len()
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.188 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728721104.A.CEE.html
推 oin1104: 我好崇拜你