1942. The Number of the Smallest Unoccupied Chair
有N個人要參加一場派對
times矩陣放的是每個人的抵達和離開時間:times[i]=[arrival_i、leave_i]
當有人到派對後會選編號最小的椅子
離開時會把椅子還回去
如果同時間有一個人離開、另一個人抵達，那他可以坐那張剛才離開的人的椅子
請回傳targetFriend坐的椅子編號
思路:
建立一個arr:arr[i]={i、arrival_i、leave_i}
接著依照arrival的時間去排序
接著建立兩個heap:heap_friend、heap_chair
heap_chair放的是目前可以坐的椅子
heap_friend放的是目前抵達的人，他的leave time和椅子編號
接著就開始從arr把人丟到heap_friend裡面
再丟之前要把離開時間小於等於arr[i]的人pop出來
並且把他坐的椅子push進heap_chair
這樣就可以得到答案了
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 smallestChair(times [][]int, targetFriend int) int {
new_times := make([][3]int, len(times))
for key, val := range times {
new_times[key][0] = key
new_times[key][1] = val[0]
new_times[key][2] = val[1]
}
slices.SortFunc(new_times, func(i, j [3]int) int {
return i[1] - j[1]
})
h1 := &Generic_heap[[2]int]{make([][2]int, 0), func(a, b [2]int) bool {
return a[1] < b[1] //[2]int{chair , leave_time}
}}
h2 := &Generic_heap[int]{make([]int, 0), func(a, b int) bool {
return a < b
}}
for i := 0; i < len(times); i++ {
heap.Push(h2, i)
}
for _, val := range new_times {
for h1.Len() > 0 && h1.data[0][1] <= val[1] {
tmp := heap.Pop(h1).([2]int)
heap.Push(h2, tmp[0])
}
if val[0] == targetFriend {
return h2.data[0]
} else {
tmp := heap.Pop(h2).(int)
heap.Push(h1, [2]int{tmp, val[2]})
}
}
return -1
}