我有一系列任務[開始、結束、期間]。
每項任務都需要在從開始到結束的時間范圍內完成，周期是完成任務所需的時間長度。
- 期間可以是不連續的時間
- 包括開頭和結尾
- 我們可以同時處理無限數量的任務。
找出處理所有任務的最短時間
示例： 輸入：
[[1,3,2],[2,5,3],[5,6,2]]
輸出：
4
解釋：
For tasks[0] we can have time points 2,3
For tasks[1] we can have time points 2, 3, 5
For tasks[2] we can time points 5, 6
所以我們只需要在 2,3,5,6 的時間點就可以完成任務。
我的做法：
int process(List<List<Integer>> list) {
Set<Integer> s = new HashSet<>();
for(List<Integer> p : list) {
int period = p.get(p.size()-1);
List<Integer> other = new ArrayList<>();
int i=0;
int s = p.get(0);
int e = p.get(1);
for(i=s; i<=e && period >=0; i ) {
if(s.contains(i)) {
period--;
} else {
other.add(i);
}
}
if(period != 0) {
for(i=other.size()-1; i>=0 && period >0; i--, period--) {
s.add(other.get(i));
}
}
}
return s.size();
}
在這里，我嘗試將任務添加到集合中，當我已經獲得了一段時間內所需的任務時，我將執行下一個任務。但我的做法是不正確的。
解決這個問題的正確方法是什么？我正在尋找一種使用 Java 或 python 的方法。
uj5u.com熱心網友回復：
計算機可以同時處理無限數量的任務。因此，您應該優先考慮計算機可以處理盡可能多任務的時間戳，直到所有任務都被消耗完。
您可以按照以下步驟操作。
創建從離散時間戳到此時可以處理的任務數的映射。
例如，時間戳 1 只能處理一個任務（#0），而時間戳 2 和時間戳 3 最多可以處理兩個任務（#0、#1）。
創建這樣的映射后，從中彈出任務數最多的時間戳。
在上述情況下，我們應該首先從映射中彈出時間戳 2，然后在下一次（下一個回圈）彈出時間戳 3。
然后，更新系結到該時間戳的剩余任務周期，并在必要時更新在步驟 1 中創建的映射。
只有當任務的剩余周期減少到 0 時，我們才需要通過將其與空閑時間戳解除系結來更新映射。這是因為任務的周期可能小于其開始時間和結束時間的持續時間。例如，在彈出時間戳2和時間戳3之后，任務#0的剩余周期變為0，但仍然存在從時間戳1到任務#0的映射。因此我們需要洗掉它。
跳至步驟 2，直到完成所有任務。
執行步驟 2 的次數是最終結果。
這是一個未優化的示例 python 代碼。
tasks = [[1,3,2],[2,5,3],[5,6,2]]
time2task = {} # Mapping from timestamp to tasks
remaing_period = [period for _, _, period in tasks]
# Step 1.
for tid, (start, end, period) in enumerate(tasks):
for ts in range(start, end 1):
time2task.setdefault(ts, set()).add(tid)
busy_ts = [] # busy timestamps
while any(remaing_period): # Condition of Step 4.
# Step 2.
ts, tids = max(time2task.items(), key=lambda item: (len(item[1]), -item[0]))
time2task.pop(ts)
busy_ts.append(ts)
# Step 3.
for tid in list(tids):
remaing_period[tid] -= 1
if remaing_period[tid] == 0:
# Correct the mapping created at step 1
start, end, _ = tasks[tid]
for idle_ts in range(start, end 1):
if idle_ts in time2task:
time2task[idle_ts].remove(tid)
if len(time2task[idle_ts]) == 0:
time2task.pop(idle_ts)
print(busy_ts)
uj5u.com熱心網友回復：
我認為你過于復雜了。我認為以下解決方案就足夠了：
int process(List<Integer> list) {
Set<Integer> s = new HashSet<>();
for(List<Integer> p : list) {
int period = p.get(p.size()-1);
int s = p.get(0);
int e = p.get(1);
for(int i=s; i<=e; i ) {
s.add(i);
}
}
return s.size();
}
此解決方案會將所有時間點添加到集合中。這不是最有效的解決方案，但它是最容易閱讀和理解的解決方案。
uj5u.com熱心網友回復：
您可以在下面找到掃描線解決方案代碼
https://leetcode.com/discuss/interview-question/2770147/an-interesting-oa-question-expedia/1671632
邏輯
我們將每個任務的開始點和結束點分開，并按時間排序。
當我們遇到一個起始點時，我們存盤它什么時候開始以及它需要多少時間。
當我們遇到一個結束點時，我們確定結束點對應的起點，并檢查它還需要多少時間。我們從我們遇到的所有活動任務中減去它的時間
例如 [1,3,2], [2,5,3],[5,6,2] --> (1,2,starting), (2,3, starting), (3,ending), ( 5,2，開始），（5，結束），（6，結束）
at time 1, we meet (1,2,starting), start at 1 and need 2 time， stack=[(1,2)]
at time 2, we meet (2,3,starting), start at 2 and need 3 time, stack=[(1,2),(2,3]
at time 3, we meet ending time 3 for (1,2). res =2 as 2 is what (1,2) left. now we remove (1,2) and substract all active tasks in stack by at most 2. for (2,3), we can take away 2 pts. stack=[(2,1)]
at time 5, we first meet (5,2,starting), start at 5 and need 2 time, stack=[(2,1),(5,2)]
at time 5, we also meet endining pt for (2,1), res =1, which is what (2,1) left, we remove (2,1) from stack and substract all active tasks in stack by at most 1. (5,2) starts at 5, it can have 1 pts at 5, so it becomes(5,1), stack=[(5,1)]
at time 6, we meet the end of (5,1), res =1, stop.
res=4
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/529179.html
標籤：Python爪哇算法