1、前言

题目描述

2、思路

这道题做起来不是很难，难在于是一个工程性的题，没有太多规律可循，只能好好梳理下解法。

首先，我们的执行是按照时间来执行的，所以我们不能以全局的角度去选择（比如会议室选取的题），只能是时间边流逝边选择。数组可能是乱序的，我们首先需要将数组排序（实际工程中，进来的任务都是有个先后，所以无需排序）。排序完毕之后，我们需要根据题目的意思，先选取耗时短的，在耗时一样的基础上，选择序号小的，所以我们需要一个先根据耗时排序，再根据序号排序的小根堆。

首先取 time 从1开始，在数组中小于 time 的都一股脑加进去。如果队列为空，说明 time 太小，直接前进到数组中最近的任务时间。如果队列不为空，直接取出任务运行，记录下运行的序号，然后跳到任务截止的时间，即 time + 任务耗时。

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};
        }

        // 根据任务入队时间进行排序
        Arrays.sort(target, (a, b) ->  a[0] - b[0]);

        // 先按照「持续时间」排序，再根据「任务编号」排序，比如 [[1, 9, 0], [6, 1, 1], [7, 1, 2]]，在 [1, 9] 执行的时候，
        // 当然要执行 [6, 1, 1],[7, 1, 2] 入队，首先应该执行 [6,1, 1]，因为它排前面
        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 表示时间，j 表示 target 数组的索引，idx 表示结果 sequence 索引
        for(int time = 1, j = 0, idx = 0; j < n; ){
            // 如果 target 数组中有比 time 时间早的，那就一股脑加入。
            // 在任务已经加完的基础上，后续只要执行取任务的方法即可。
            while(j < n && target[j][0] <= time){
                priorityQueue.add(target[j++]);
            }

            // 队列为空的情况下，直接跳到最近的时间
            if(priorityQueue.isEmpty()){
                time = target[j][0];
            }else {
                // 队列不为空的情况下，快速执行完毕，然后跳到执行完毕的时间
                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}
        });
    }
}