1、前言

題目描述

2、思路

這道題做起來(lái)不是很難，難在于是一個(gè)工程性的題，沒(méi)有太多規(guī)律可循，只能好好梳理下解法。

首先，我們的執(zhí)行是按照時(shí)間來(lái)執(zhí)行的，所以我們不能以全局的角度去選擇（比如會(huì)議室選取的題），只能是時(shí)間邊流逝邊選擇。數(shù)組可能是亂序的，我們首先需要將數(shù)組排序（實(shí)際工程中，進(jìn)來(lái)的任務(wù)都是有個(gè)先后，所以無(wú)需排序）。排序完畢之后，我們需要根據(jù)題目的意思，先選取耗時(shí)短的，在耗時(shí)一樣的基礎(chǔ)上，選擇序號(hào)小的，所以我們需要一個(gè)先根據(jù)耗時(shí)排序，再根據(jù)序號(hào)排序的小根堆。

首先取 time 從1開(kāi)始，在數(shù)組中小于 time 的都一股腦加進(jìn)去。如果隊(duì)列為空，說(shuō)明 time 太小，直接前進(jìn)到數(shù)組中最近的任務(wù)時(shí)間。如果隊(duì)列不為空，直接取出任務(wù)運(yùn)行，記錄下運(yùn)行的序號(hào)，然后跳到任務(wù)截止的時(shí)間，即 time + 任務(wù)耗時(shí)。

3、代碼

public class Q1834_GetOrder {

    public int[] getOrder(int[][] ts) {
        if(ts == null || ts.length == 0){
            return new int[]{};
        }

        int n = ts.length;

        int[][] target = new int[n][3];
        for (int i = 0; i < ts.length; i++) {
            target[i] = new int[]{ts[i][0], ts[i][1], i};
        }

        // 根據(jù)任務(wù)入隊(duì)時(shí)間進(jìn)行排序
        Arrays.sort(target, (a, b) ->  a[0] - b[0]);

        // 先按照「持續(xù)時(shí)間」排序，再根據(jù)「任務(wù)編號(hào)」排序，比如 [[1, 9, 0], [6, 1, 1], [7, 1, 2]]，在 [1, 9] 執(zhí)行的時(shí)候，
        // 當(dāng)然要執(zhí)行 [6, 1, 1],[7, 1, 2] 入隊(duì)，首先應(yīng)該執(zhí)行 [6,1, 1]，因?yàn)樗徘懊?        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> {
            int compare = a[1] - b[1];
            if(compare == 0){
                compare = a[2] - b[2];
            }
            return compare;
        });


        int[] sequence = new int[n];

        // time 表示時(shí)間，j 表示 target 數(shù)組的索引，idx 表示結(jié)果 sequence 索引
        for(int time = 1, j = 0, idx = 0; j < n; ){
            // 如果 target 數(shù)組中有比 time 時(shí)間早的，那就一股腦加入。
            // 在任務(wù)已經(jīng)加完的基礎(chǔ)上，后續(xù)只要執(zhí)行取任務(wù)的方法即可。
            while(j < n && target[j][0] <= time){
                priorityQueue.add(target[j++]);
            }

            // 隊(duì)列為空的情況下，直接跳到最近的時(shí)間
            if(priorityQueue.isEmpty()){
                time = target[j][0];
            }else {
                // 隊(duì)列不為空的情況下，快速執(zhí)行完畢，然后跳到執(zhí)行完畢的時(shí)間
                int[] cur = priorityQueue.poll();
                sequence[idx++] = cur[2];
                time += cur[0];
            }

        }

        return sequence;
    }


    public static void main(String[] args) {
        new Q1834_GetOrder().getOrder(new int[][]{
                {1,2}, {2, 4}, {3, 2}, {4, 1}
        });
    }
}