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 } -- ※ 發信站: 批踢踢實業坊(pttweb.org.tw), 來自: 111.71.214.188 (臺灣) ※ 文章網址: https://pttweb.org.tw/Marginalman/M.1728642879.A.B8B

推 oin1104: 大師 我好崇拜你 10/11 18:35

推 orangeNoob: 剩我想不到要用heap了 10/11 18:45

推 dont: 大師 10/11 19:04