當前位置:網站首頁>【leectode 2022.1.22】批量處理任務
【leectode 2022.1.22】批量處理任務
2022-01-28 02:46:58 【程序猿不脫發2】
某實驗室計算機待處理任務以 [start,end,period] 格式記於二維數組 tasks,錶示完成該任務的時間範圍為起始時間 start 至結束時間 end 之間,需要計算機投入 period 的時長,注意:
period 可為不連續時間
首尾時間均包含在內
處於開機狀態的計算機可同時處理任意多個任務,請返回電腦最少開機多久,可處理完所有任務。
示例 1:
輸入:tasks = [[1,3,2],[2,5,3],[5,6,2]]
輸出:4
解釋:
tasks[0] 選擇時間點 2、3;
tasks[1] 選擇時間點 2、3、5;
tasks[2] 選擇時間點 5、6;
因此計算機僅需在時間點 2、3、5、6 四個時刻保持開機即可完成任務。
示例 2:
輸入:tasks = [[2,3,1],[5,5,1],[5,6,2]]
輸出:3
解釋:
tasks[0] 選擇時間點 2 或 3;
tasks[1] 選擇時間點 5;
tasks[2] 選擇時間點 5、6;
因此計算機僅需在時間點 2、5、6 或 3、5、6 三個時刻保持開機即可完成任務。
提示:
2 <= tasks.length <= 10^5
tasks[i].length == 3
0 <= tasks[i][0] <= tasks[i][1] <= 10^9
1 <= tasks[i][2] <= tasks[i][1]-tasks[i][0] + 1
java代碼:
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class Pair {
public int slots;
public int index;
public Pair(int slots, int index) {
this.slots = slots;
this.index = index;
}
}
class PairComparator implements Comparator<Pair> {
@Override
public int compare(Pair p1, Pair p2) {
if (p1.slots > p2.slots || (p1.slots == p2.slots && p1.index > p2.index)) {
return 1;
} else if (p1.slots < p2.slots || p1.index < p2.index) {
return -1;
}
return 0;
}
}
class Solution {
public int processTasks(int[][] tasks) {
int n = tasks.length;
var ts = new TreeSet<Integer>();
for (var task : tasks) {
ts.add(task[0]);
ts.add(task[1] + 1);
}
var vt = new ArrayList<>(ts);
int m = vt.size();
var mp = new HashMap<Integer, Integer>(m);
for (int i = 0; i < m; ++i) {
mp.put(vt.get(i), i);
}
var starts = Stream.generate(ArrayList<Integer>::new)
.limit(m)
.collect(Collectors.toList());
for (int i = 0; i < n; ++i) {
starts.get(mp.get(tasks[i][0])).add(i);
}
int ans = 0;
int extra = 0;
var pq = new PriorityQueue<Pair>(n, new PairComparator());
for (int i = 0; i < m - 1; ++i) {
while (!pq.isEmpty() && tasks[pq.peek().index][1] < vt.get(i)) {
pq.poll();
}
for (int u : starts.get(i)) {
pq.add(new Pair(extra + tasks[u][1] - vt.get(i) + 1 - tasks[u][2], u));
}
int currentSeg = vt.get(i + 1) - vt.get(i);
if (!pq.isEmpty()) {
int minSlots = pq.peek().slots - extra;
int slotsToDel = currentSeg;
if (minSlots < currentSeg) {
int delta = currentSeg - minSlots;
ans += delta;
slotsToDel -= delta;
}
extra += slotsToDel;
}
}
return ans;
}
}
版權聲明
本文為[程序猿不脫發2]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201280246583350.html
邊欄推薦
猜你喜歡
隨機推薦
- uniapp上傳圖片及組件傳值
- 瑞利年金險資金保障安全嗎?收益高不高啊?
- 華為手機USB連不上電腦的解决方法
- Flutter 2,移動金融應用開發
- 關於st25系列NFC標簽簡單介紹及st25TV系列用於門禁讀取時的注意事項總結
- 關於用ffmpeg轉手機視頻發現視頻長寬倒了的問題
- 函數 / 類模板--模板2
- 數組中的第k個最大的元素--優先級隊列、排序、堆、排序
- 單片機實例27——ADC0809A/D轉換器基本應用技術(硬件電路圖+匯編程序+C語言程序)
- Collection集合的學習
- 一場面試結束,某度員工從事Android 5年為何還是初級工程師?
- 3本書閱讀筆記【人月神話-Go語言實戰-研發能力持續成長路線】01
- PHP垃圾回收機制
- 【電子技術】什麼是LFSR?
- 死鎖?如何定比特到死鎖?如何修複死鎖?(jps和jstack兩個工具)
- 快樂寒假 22/01/20
- image
- 噴程序員?SURE?
- LDO分壓電阻計算小工具
- 面試之求一串字符串中每個字符的出現次數
- 【ISO15765_UDS&OBD診斷】-01-概述
- 【Mysql上分之路】第九篇:Mysql存儲引擎
- RHCE 第一次作業
- 2021.10.16我的第一篇博客:一切皆有可能!
- CTA-敏感行為-讀取IMEI
- 面試被問怎麼排查平時遇到的系統CPU飆高和頻繁GC,該怎麼回答?
- nuxt項目總結-綜合
- 自然語言處理學習筆記(一)
- C語言第一課
- 各比特大佬,Spark的重點難點系列暫時更新完畢
- 基於 esbuild 的 universal bundler 設計
- XCTFre逆向(四):insanity
- 理解什麼是真正的並發數
- JVM腦圖
- 【Pytorch(四)】學習如何使用 PyTorch 讀取並處理數據集
- 函數棧幀的創建與銷毀
- 構建神經網絡- 手寫字體識別案例
- 多模態生成模型ERNIE-VILG
- kotlin不容忽視的小細節
- 備戰一年,終於斬獲騰訊T3,我堅信成功是可以複制的