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
}