- 25min come up with solution: Https://expl.ai.TEHUMSC
- T.C.: O(nlogn) + O(nlogk)
- One small error: Don't mod result before finishing
class Solution:
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
modNum = 10 ** 9 + 7
effiSpee = sorted(zip(efficiency, speed))
minHeap = []
heapSum = 0
result = 0
for i in reversed(range(n)):
thisEffi, thisSpee = effiSpee[i]
heapq.heappush(minHeap, (thisSpee, thisEffi))
heapSum += thisSpee
if len(minHeap) > k:
topSpeed, topEffi = heapq.heappop(minHeap)
heapSum -= topSpeed
result = max(result, heapSum * thisEffi)
return result % modNum
- 15 min come up with solution: https://expl.ai/TXGGTSP
- Four attempts before reaching the correct solution ......
- Did not handle the case where cpu could be idle
- When cpu is idle, increment the timer instead of directly jumping to the correct ts, resulting in TLE.
- Similar to 2, but only set the start time, not update time.
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
if len(tasks) == 0:
return []
tupleList = []
for i in range(len(tasks)):
tupleList.append((tasks[i][0], tasks[i][1], i))
sortedT = sorted(tupleList)
ptr = 0
currT = sortedT[0][0]
minHeap = []
result = []
while len(result) < len(tasks):
while ptr < len(sortedT) and sortedT[ptr][0] <= currT:
heapq.heappush(minHeap, (sortedT[ptr][1], sortedT[ptr][2]))
ptr += 1
if len(minHeap) != 0:
proTime, index = heapq.heappop(minHeap)
result.append(index)
currT += proTime
else:
currT = max(currT, sortedT[ptr][0])
return result