IPO (首次公开发行)拍卖采访问题的解决方案

Question

​

​

*TLDR：

输入：

bids =表示userid、#share、$bid、时间戳的ints列表

totalShares =要分配的股票总数。

TODO:在投标人之间分配股份，并将0股的投标人返还给用户。股票分配逻辑: 1)出价最高的投标人获得他们所竞购的所有股份，然后2)如果在竞价中有关联，将股份转让给较早的投标人。

对于上面的问题，我觉得我想出的解决方案比较简单，但似乎通过了我能想到的所有边缘情况。我能想到的唯一值得怀疑的情况是

• 的投标价格和投标时间是相同的，没有足够的股份供所有投标人使用，即:出价= [0, 2 ,10,0，1,2,10,0]和totalShares =2。我不清楚是否应该给每个出价1股，或者用户if 0只得到两者。

有人看到我的解决方案是否可以在任何时候被优化吗？

def getUnallocatesUsers(bids, totalShares):
  s = 0
  for b in bids:
      s += b[1]  
  if totalShares >= s: return []  # no losers because enough shares to go around

  bids.sort(key = lambda x: (-x[2],x[3]))  # sort by highest bid, then timestamp for ties
  losers = []
  for b in bids:
    if totalShares <= 0: losers.append(b[0])
    else:
      totalShares -= b[1]
  return losers

Answer 1

你的解决方案不能解决循环往复的问题。如果有一个以上的出价相同的价格，你将需要给每个用户至少一个份额，直到和迭代的用户。

Answer 2

根据问题，情况是：bids = [[0,2,10,0], [1,2,10,0]]应该返回[]。因为有一个平局，每个人都可以分配一个份额。我建议使用heapq和一个额外的数组来处理tie。