【leectode 2022.1.22】批量處理任務

某實驗室計算機待處理任務以 [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;
    }
}