2136. 全部开花的最早一天 (opens new window)

1.贪心+调度优化

本题主要考验调度思路，以及思维角度。

考虑是否有必要交替播种？

显然只看播种时间，由于播种行为只能串行进行，因此总播种时间是固定的。

假设存在某一种最优化的交替播种1122312321，那么这种情况实际上可以优化为3322221111，可以发现后者播种方式中3号和2号的生长期都被提前，因此后一种播种顺序必定是优于交替播种方式(总时间小于等于交替播种)。

播种顺序

经过前面讨论可以得知，调度序列必然是i,i,i,k,k,k,j,j,j...也就是播种完一种植物后，再播种另一种植物。因此最终问题就落到了应该以什么顺序播种的问题？

直观上来想，我们尽可能的希望“生长时间”长的植物优先播种，这样在生长时间内播种越多植物，那么总时间应该是越少的。——经过证明也确实如此。

总时间=播种时间之和+“并行生长时间”。其中并行生长时间中，当多个植物的生长时间并行程度越高，这部分花的时间必定越少。

class Solution {
    public int earliestFullBloom(int[] plantTime, int[] growTime) {
        Integer[] nums=new Integer[plantTime.length];
        for(int i=0;i<nums.length;i++){
            nums[i]=i;
        }
        Arrays.sort(nums,new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return growTime[o2]-growTime[o1];
            }
        });
        int res=0,curr=0;
        for(int i=0;i<nums.length;i++){
            int inx=nums[i];
            res+=plantTime[inx];
            if(plantTime[inx]+growTime[inx]>curr){
                curr=growTime[inx];
            }
            else{
                curr-=plantTime[inx];
            }
        }
        return res+curr;
    }
}