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()
}

我好崇拜你