queue := PriorityQueue{} time := 0 for _, c := range courses { if time + c[0] <= c[1] { queue.Push(c[0]) time += c[0] } elseif !queue.IsEmpty() && queue.Top() > c[0] { time += c[0] - queue.Poll() queue.Push(c[0]) } }
return queue.Size() }
问题是，这里面需要 sort 和 PriorityQueue。Python、Java、甚至 C++ 写这个都还是比较方便的，直接用标准库里的实现。但 Golang，，，标准库的这两个东西有点诡异，用起来没那么方便。
funcquick_sort_sint(pA *([]int), pint, rint, lefunc(a, b interface{})bool) { var interfaceSlice []interface{} = make([]interface{}, len(*pA)) for i, d := range *pA { interfaceSlice[i] = d } quick_sort(&interfaceSlice, p, r, le) for i, v := range interfaceSlice { (*pA)[i] = v.(int) } }
funcquick_sort_ssint(pA *([][]int), pint, rint, lefunc(a, b interface{})bool) { var interfaceSlice []interface{} = make([]interface{}, len(*pA)) for i, d := range *pA { interfaceSlice[i] = d } quick_sort(&interfaceSlice, p, r, le) for i, v := range interfaceSlice { (*pA)[i] = v.([]int) } }
queue := PriorityQueue{} time := 0 for _, c := range courses { if time + c[0] <= c[1] { queue.push(c[0]) time += c[0] } elseif !queue.isEmpty() && queue.top() > c[0] { time += c[0] - queue.poll() queue.push(c[0]) } }
funcquick_sort_sint(pA *([]int), pint, rint, lefunc(a, b interface{})bool) { var interfaceSlice []interface{} = make([]interface{}, len(*pA)) for i, d := range *pA { interfaceSlice[i] = d } quick_sort(&interfaceSlice, p, r, le) for i, v := range interfaceSlice { (*pA)[i] = v.(int) } }
/** 把对 [][]int 的快排转化为对 []interface{} 的快排 **/
funcquick_sort_ssint(pA *([][]int), pint, rint, lefunc(a, b interface{})bool) { var interfaceSlice []interface{} = make([]interface{}, len(*pA)) for i, d := range *pA { interfaceSlice[i] = d } quick_sort(&interfaceSlice, p, r, le) for i, v := range interfaceSlice { (*pA)[i] = v.([]int) } }
/** 对 []interface{} 的快排 **/
funcquick_sort(pA *([]interface{}), pint, rint, lefunc(a, b interface{})bool) { if p >= r { return } q := partition(pA, p, r, le) quick_sort(pA, p, q-1, le) quick_sort(pA, q+1, r, le) }
funcpartition(pA *([]interface{}), pint, rint, lefunc(a, b interface{})bool) int { A := (*pA)
q := p for u := p; u < r; u++ { if le(A[u], A[r]) { A[q], A[u] = A[u], A[q] q++ } } A[q], A[r] = A[r], A[q] return q }
funcmerge(pA *[][]int, p, q, r int, le func (a, b []int)bool) { // n1 := q - p + 1 // n2 := r - q // b, c := make([][]int, n1+1), make([][]int, n2+1) A := *pA
b := append(make([][]int, 0), A[p: q+1]...) c := append(make([][]int, 0), A[q+1: r+1]...)
b = append(b, INF) c = append(c, INF) i, j := 0, 0 for k := p; k <= r; k++ { if le(b[i], c[j]) { A[k] = b[i] i++ } else { A[k] = c[j] j++ } } }
funcmergeSort(pA *[][]int, p int, r int, le func (a, b []int)bool) { if p >= r { return } q := (p + r) / 2 mergeSort(pA, p, q, le) mergeSort(pA, q+1, r, le) merge(pA, p, q, r, le) }
这个代码写的时候要注意一点，b 和 c 这里，不能直接这样：
1 2
b := append(A[p: q+1], INF) c := append(A[q+1: r+1], INF)
原因是，切片和底层数组。你构建 b 的时候往里面 append 了一个 INF，实际上是底层数组的A[q+1] 位置变成了 INF，所以再构建 c 的时候，切片 A[q+1: r+1] 的值就成了 [INF, ...]，然后归并就爆炸了💥。
queue := PriorityQueue{} time := 0 for _, c := range courses { if time + c[0] <= c[1] { queue.Push(c[0]) time += c[0] } elseif !queue.IsEmpty() && queue.Top() > c[0] { time += c[0] - queue.Poll() queue.Push(c[0]) } }
funcinsertSortReverse(pA *[]int) { A := *pA for i := 1; i < len(A); i++ { key := A[i] j := i - 1 for j >= 0 && A[j] < key { A[j+1] = A[j] j -= 1 } A[j+1] = key } }
/** 对 [][]int 的归并排序 **/
var INF = []int{99999999, 99999999}
funcmerge(pA *[][]int, p, q, r int, le func (a, b []int)bool) { // n1 := q - p + 1 // n2 := r - q // b, c := make([][]int, n1+1), make([][]int, n2+1) A := *pA
b := append(make([][]int, 0), A[p: q+1]...) c := append(make([][]int, 0), A[q+1: r+1]...)
b = append(b, INF) c = append(c, INF) i, j := 0, 0 for k := p; k <= r; k++ { if le(b[i], c[j]) { A[k] = b[i] i++ } else { A[k] = c[j] j++ } } }
funcmergeSort(pA *[][]int, p int, r int, le func (a, b []int)bool) { if p >= r { return } q := (p + r) / 2 mergeSort(pA, p, q, le) mergeSort(pA, q+1, r, le) merge(pA, p, q, r, le) }
这一个版本就可以通过了：
标准库 sort + heap
Go 的标准库还是很强大的，但是标准库的设计相当的 Golang，才从其他语言转过来用着真的很不习惯（比如 math 包里连 Max 都没有），不过多用用这些东西、多看看它们的源码（Go 标准库的好多源码写的挺有意思的），对理解 Go 的思想很有帮助。
到这里对 [][]int 排序的需求可以解决了，but we do need one more thing.
Go 还提供了一种更加 Go 风格的排序：sort.Sort。
func Sort(data Interface)
Sort sorts data. It makes one call to data.Len to determine n, and O(n*log(n)) calls to data.Less and data.Swap. The sort is not guaranteed to be stable.
这玩意儿是传一个 sort.Interface 的实现进来，这真的很 Golang！
1 2 3 4 5 6 7 8 9 10
type Interface interface { // Len is the number of elements in the collection. Len() int // Less reports whether the element with // index i should sort before the element with index j. Less(i, j int) bool // Swap swaps the elements with indexes i and j. Swap(i, j int) }
Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.
The minimum element in the tree is the root, at index 0.
A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.
// This example demonstrates a priority queue built using the heap interface. package main
import ( "container/heap" "fmt" )
// An Item is something we manage in a priority queue. type Item struct { value string// The value of the item; arbitrary. priority int// The priority of the item in the queue. // The index is needed by update and is maintained by the heap.Interface methods. index int// The index of the item in the heap. }
// A PriorityQueue implements heap.Interface and holds Items. type PriorityQueue []*Item
func(pq PriorityQueue)Len()int { returnlen(pq) }
func(pq PriorityQueue)Less(i, j int)bool { // We want Pop to give us the highest, not lowest, priority so we use greater than here. return pq[i].priority > pq[j].priority }
// update modifies the priority and value of an Item in the queue. func(pq *PriorityQueue)update(item *Item, value string, priority int) { item.value = value item.priority = priority heap.Fix(pq, item.index) }
// This example creates a PriorityQueue with some items, adds and manipulates an item, // and then removes the items in priority order. funcmain() { // Some items and their priorities. items := map[string]int{ "banana": 3, "apple": 2, "pear": 4, }
// Create a priority queue, put the items in it, and // establish the priority queue (heap) invariants. pq := make(PriorityQueue, len(items)) i := 0 for value, priority := range items { pq[i] = &Item{ value: value, priority: priority, index: i, } i++ } heap.Init(&pq)
// Insert a new item and then modify its priority. item := &Item{ value: "orange", priority: 1, } heap.Push(&pq, item) pq.update(item, item.value, 5)
// Take the items out; they arrive in decreasing priority order. for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) fmt.Printf("%.2d:%s ", item.priority, item.value) } }
