完成工作的最短時間
「完成作業的最短時間」問題的詳細指南和 Python 實作。
1. 學習
「完成工作的最短時間」問題是貪婪部分的關鍵挑戰。
此實作著重於 Python 中的簡單層級邏輯。
在我們提供的解決方案中，我們優先考慮技術準確性和程式碼可讀性。
2. Real-World Applications
3. Visual Intuition
視覺化完成作業的最短時間的邏輯流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔細閱讀完成作業的最短時間的問題陳述。
2. Formulate brute force
起草一個簡單的迭代解決方案。
3. Identify inefficiency
尋找冗餘計算。
4. Optimize search path
使用散列或排序來加速該過程。
5. Final Implementation
清理生產標準代碼。
問題陳述
寫一個函數 min_time_jobs(jobs, k, t) 來找出完成所有作業的最短時間。陣列 jobs 表示完成每個作業所需的時間。有 k 受讓人，每個受讓人花費 t 單位時間來完成 1 單位作業。作業只能作為連續的子段分配給受讓人。
- •1 <= len(jobs) <= 10^5
- •1 <= k <= len(jobs)
- •1 <= t <= 1000
- •1 <= jobs[i] <= 10^4
範例
min_time_jobs([10, 7, 8, 12, 8, 5, 9], 4, 5)
100
Optimal contiguous assignment: [10, 7], [8, 12], [8, 5], [9]. Max job units assigned is 20 (8+12). Time = 20 * 5 = 100.
min_time_jobs([4, 5, 10], 2, 1)
10
Optimal contiguous assignment: [4, 5], [10]. Max job units assigned is 10. Time = 10 * 1 = 10.
Need a Hint?
Edge Cases to Watch
- 空輸入結構
- 單元素輸入
- 大數值範圍
準備好解決了嗎？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面試見解和變化
複雜度分析分解
為什麼時間: Directly evaluates all possibilities.
為什麼選擇太空: Uses standard local memory.
為什麼時間: Optimized paths reduce total operations.
為什麼選擇太空: May trade memory for speed.
最佳化解決方案Python程式碼
最佳化解決方案Python程式碼
def min_time_opt(jobs, k):
def can_finish(limit):
workers = [0] * k
def solve(i):
if i == len(jobs): return True
for j in range(k):
if workers[j] + jobs[i] <= limit:
workers[j] += jobs[i]
if solve(i + 1): return True
workers[j] -= jobs[i]
if workers[j] == 0: break
return False
return solve(0)
jobs.sort(reverse=True)
l, r = max(jobs), sum(jobs); res = r
while l <= r:
m = (l + r) // 2
if can_finish(m): res = m; r = m - 1
else: l = m + 1
return res暴力破解代碼（劇透保護）
暴力破解代碼（劇透保護）
def min_time_brute(jobs, k):
res = float('inf')
def solve(i, workers):
nonlocal res
if i == len(jobs): res = min(res, max(workers)); return
for j in range(k):
workers[j] += jobs[i]; solve(i + 1, workers); workers[j] -= jobs[i]
solve(0, [0]*k); return resAlgorithm Pattern Checklist
When dealing with Greedy data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推薦的 Python 資源
透過相關的互動式教學、備忘單和程式碼比較來擴展您的知識。
Python 生成器：記憶體高效的迭代器
了解如何使用Python生成器和yield语句以最小的内存占用处理巨大的数据集。掌握生成器表達式。
如何在 Python 中將字串轉換為 Int（安全轉換和基數）
了解如何在 Python 中使用 int() 函數將字串轉換為整數。安全地處理錯誤並將數字從二進位、八進位或十六進位轉換。
Python 日期時間格式備忘單
了解如何在 Python 中使用 datetime、strftime 和 strptime 解析和格式化日期和時間。
Python 裝飾器與裝飾器設計模式：主要區別
比較 Python 裝飾器和經典的裝飾器設計模式。了解定義時函數包裝和使用可運行程式碼的執行時間動態物件組合之間的差異。