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