[GO] Use two heaps
Intuition\n\nThis is a typical use case to find maximum and minimum elements with heap. The buy orders are the ones which we would like to find its highest pric
# Intuition\n\nThis is a typical use case to find maximum and minimum elements with heap. The buy orders are the ones which we would like to find its highest price at any point of time, and thus is a maximum heap, and similarly, the sell orders are the ones which we would like to find its lowest price at any point of time, and thus is a minimum heap.\n\n# Approach\n\n1. For any new buy order, we look at: a) whethere there is any sell orders, if no, push into buy orders heap. b) is the sell order within the price range, if no, push into buy orders heap. c) if it is within the range, then simply update the amount in the corresponding sell order, and pop it up if it is 100% fullfilled. d) if this buy order is not 100% fullfilled, continue to the next loop\n2. For any new sell order, we look at: a) whethere there is any buy orders, if no, push into sell orders heap. b) is the buy order within the price range, if no, push into sell orders heap. c) if it is within the range, then simply update the amount in the corresponding buy order, and pop it up if it is 100% fullfilled. d) if this sell order is not 100% fullfilled, continue to the next loop.\n\n# Complexity\n- Time complexity: $$O(n log n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nfunc getNumberOfBacklogOrders(orders [][]int) int {\n    var sells = &sellAsc{}\n\tvar buys = &buyDesc{}\n\n\tfor i, o := range orders {\n\t\tif o[2] == 0 {\n\t\t\t// this is a buy order, find the smallest sell order\n\t\t\tfor {\n\n\t\t\t\tif len(*sells) == 0 {\n\t\t\t\t\theap.Push(buys, order{price: o[0], amount: o[1], term: i})\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t\tpeek := (*sells)[0]\n\t\t\t\tif peek.price > o[0] {\n\t\t\t\t\theap.Push(buys, order{price: o[0], amount: o[1], term: i})\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t\t// can be fullfilled\n\t\t\t\tif peek.amount > o[1] {\n\t\t\t\t\t(*sells)[0].amount = peek.amount - o[1]\n\t\t\t\t\to[1] = 0\n\t\t\t\t} else {\n\t\t\t\t\theap.Pop(sells)\n\t\t\t\t\to[1] = o[1] - peek.amount\n\t\t\t\t}\n\t\t\t\tif o[1] == 0 {\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t} else {\n\t\t\t// this is a sell order, find the largest buy order\n\t\t\tfor {\n\t\t\t\tif len(*buys) == 0 {\n\t\t\t\t\theap.Push(sells, order{price: o[0], amount: o[1], term: i})\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t\tpeek := (*buys)[0]\n\t\t\t\tif peek.price < o[0] {\n\t\t\t\t\theap.Push(sells, order{price: o[0], amount: o[1], term: i})\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t\t// can be fullfilled\n\t\t\t\tif peek.amount > o[1] {\n\t\t\t\t\t(*buys)[0].amount = peek.amount - o[1]\n\t\t\t\t\to[1] = 0\n\t\t\t\t} else {\n\t\t\t\t\theap.Pop(buys)\n\t\t\t\t\to[1] = o[1] - peek.amount\n\t\t\t\t}\n\t\t\t\tif o[1] == 0 {\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\tvar left int\n\tfor _, o := range *buys {\n\t\tleft = left + o.amount\n\t\tif left >= 1000000007 {\n\t\t\tleft = left % 1000000007\n\t\t}\n\t}\n\tfor _, o := range *sells {\n\t\tleft = left + o.amount\n\t\tif left >= 1000000007 {\n\t\t\tleft = left % 1000000007\n\t\t}\n\t}\n\treturn left\n}\n\ntype order struct {\n\tamount int\n\tprice  int\n\tterm   int\n}\n\ntype sellAsc []order\n\nfunc (s sellAsc) Len() int {\n\treturn len(s)\n}\n\nfunc (s sellAsc) Less(i, j int) bool {\n\tif s[i].price < s[j].price {\n\t\treturn true\n\t}\n\tif s[i].price > s[j].price {\n\t\treturn false\n\t}\n\treturn s[i].term < s[j].term\n}\n\nfunc (s sellAsc) Swap(i, j int) {\n\ts[i], s[j] = s[j], s[i]\n}\n\nfunc (s *sellAsc) Push(x interface{}) {\n\t*s = append(*s, x.(order))\n}\n\nfunc (s *sellAsc) Pop() interface{} {\n\told := *s\n\tn := len(old)\n\to := old[n-1]\n\t*s = old[:n-1]\n\treturn o\n}\n\ntype buyDesc []order\n\nfunc (b buyDesc) Len() int {\n\treturn len(b)\n}\n\nfunc (b buyDesc) Less(i, j int) bool {\n\tif b[i].price > b[j].price {\n\t\treturn true\n\t}\n\tif b[i].price < b[j].price {\n\t\treturn false\n\t}\n\treturn b[i].term < b[j].term\n}\n\nfunc (b buyDesc) Swap(i, j int) {\n\tb[i], b[j] = b[j], b[i]\n}\n\nfunc (b *buyDesc) Push(x interface{}) {\n\t*b = append(*b, x.(order))\n}\n\nfunc (b *buyDesc) Pop() interface{} {\n\told := *b\n\tn := len(old)\n\to := old[n-1]\n\t*b = old[:n-1]\n\treturn o\n}\n```
['Go']