Facebook
From Ample Pelican, 4 Years ago, written in Plain Text.
This paste is a reply to Untitled from Innocent Baboon - view diff
Embed
Download Paste or View Raw
Hits: 225
  1. import heapq
  2.  
  3. def getAvgWaitTime(n, cust):
  4.     heap = []
  5.     curTime = 0
  6.     waitTime = 0
  7.     cust = sorted(cust)
  8.     i = 0
  9.  
  10.     while i < n:
  11.         if curTime < cust[i][0]:
  12.             curTime = cust[i][0]
  13.         while i < n and (curTime >= cust[i][0]):
  14.             heapq.heappush(heap, (cust[i][1], cust[i][0]))
  15.             i += 1
  16.  
  17.         while (i < n) and curTime < cust[i][0] and len(heap) > 0:
  18.             time, wait = calculateWaiting(heap, curTime)
  19.             curTime += time
  20.             waitTime += wait
  21.  
  22.     # Clear all the jobs
  23.     while len(heap) > 0:
  24.         time, wait = calculateWaiting(heap, curTime)
  25.         curTime += time
  26.         waitTime += wait
  27.  
  28.     return waitTime / n
  29.  
  30.  
  31. def calculateWaiting(heap, curTime):
  32.     wait = 0
  33.     cur = heapq.heappop(heap)
  34.     wait = curTime - cur[1] + cur[0]
  35.     return (cur[0], wait)
  36.  
  37.  
  38. n = int(raw_input().strip())
  39. cust = []
  40. for i in range(n):
  41.     ar = map(int, raw_input().strip().split(' '))
  42.     cust.append((ar[0], ar[1]))
  43.  
  44.  
  45. result = getAvgWaitTime(n, cust)
  46. print(result)

Replies to Re: Untitled rss

Title Name Language When
Re: Re: Untitled Insensitive Tern text 4 Years ago.