Sort+PQ
502.IPO （M+）
Brute force EE link with Treemap: https://drive.explaineverything.com/thecode/VKVPTJN
Improved nlogn EE link with linear array: https://expl.ai/CGYXYTF
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 % modNum15 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 resultLast updated