資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢完成K個任務的最大時間
假設我們有一個任務矩陣，其中每一行有3個值。我們還有另一個值k。我們必須從任務中選擇k行，稱為S，使得以下和最小化並返回該和作為：最大值(S[0, 0], S[1, 0], ...S[k - 1, 0]) + 最大值(S[0, 1], S[1, 1], ...S[k - 1, 1]) + 最大值(S[0, 2], S[1, 2], ...S[k - 1, 2]) 我們也可以這樣說：每3列都貢獻一個成本，並透過取S中該列的最大值來計算。空列表的最大值為0。
因此，如果輸入類似於 tasks = [[2, 3, 3], [4, 5, 2], [4, 2, 3] ], k = 2，則輸出將為10，因為如果我們選擇第一行和最後一行。總和將為 S = [[2,3,3],[4,2,3]] max(S[0,0], S[1,0]) = 4 + max(S[0,1], S[1,1]) = 3 + max(S[0,2], S[1,2]) = 3 = 10
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 util() 。它將接收B
- 對列表B進行排序
- yheap := 一個列表，對於每個i在0到K-1範圍內，包含 -B[i, 1]
- 堆化yheap
- ans := B[K - 1, 0] + (-yheap[0])
- 對於i從K到B的大小，執行以下操作
- x := B[i, 0]
- 用 -B[i,1] 替換yheap
- 設定yheap的大小與K相同
- y := -yheap[0]
- ans := ans 和 x + y 的最小值
- 返回ans
- 從主方法執行以下操作：
- 如果A為空或K為0，則
- 返回0
- 對列表A進行排序
- B := 為每個i在0到K-1範圍內建立一個包含 [A[i, 1], A[i, 2]] 的對列表
- ans := A[K - 1, 0] + 每個 (y, z) 在 B 中的 y 的最大值 + 每個 (y, z) 在 B 中的 z 的最大值
- 對於i從K到A的大小，執行以下操作
- 將 [A[i][1], A[i][2]] 插入到B中
- ans = ans 和 A[i, 0] + util(B) 的最小值
- 返回ans
讓我們看看下面的實現，以便更好地理解：
示例
import heapq class Solution: def solve(self, A, K): if not A or not K: return 0 def util(B): B.sort() yheap = [-B[i][1] for i in range(K)] heapq.heapify(yheap) ans = B[K - 1][0] + (-yheap[0]) for i in range(K, len(B)): x = B[i][0] heapq.heappushpop(yheap, -B[i][1]) assert len(yheap) == K y = -yheap[0] ans = min(ans, x + y) return ans A.sort() B = [[A[i][1], A[i][2]] for i in range(K)] ans = A[K - 1][0] + max(y for y, z in B) + max(z for y, z in B) for i in range(K, len(A)): B.append([A[i][1], A[i][2]]) ans = min(ans, A[i][0] + util(B)) return ans ob = Solution() tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ] k = 2 print(ob.solve(tasks, k))
輸入
tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ], k = 2
輸出
10
更新於: 2020年10月19日
314 次瀏覽
廣告