【算法题】高效的任务规划

喜欢ヅ旅行 2024-03-27 11:01 46阅读 0赞

### [高效的任务规划][Link 1] ###

![在这里插入图片描述][5ca6c222f1904f0abdda833607eeb9d7.png]

package dynamicProgramming;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.stream.Collectors;
    
    /**
     * 高效的任务规划
     * 2
     * 3
     * 1 3
     * 2 4
     * 3 6
     * 3
     * 1 3
     * 2 4
     * 3 6
     */
    public class EfficientTaskPlanning {
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            List<Integer> res = new ArrayList<>();
    
            // 处理m组数据
            int m = Integer.parseInt(bf.readLine());
            for (int j = 0; j < m; j++) {
        
                // 收集1组机器的n台机器
                int n = Integer.parseInt(bf.readLine());
                int[][] machines = new int[n][2];
                for (int i = 0; i < n; i++) {
        
                    int[] machine = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                    machines[i] = machine;
                }
    
                // 算每组数据的最短用时
                int minTime = minTime(n, machines);
                res.add(minTime);
            }
            bf.close();
            String collect = res.stream().map(String::valueOf).collect(Collectors.joining(","));
            System.out.println(collect);
        }
    
        private static int minTime(int n, int[][] machines) {
        
            // 运行时间降序，运行时间相同则补数时间升序
            Arrays.sort(machines, (a, b) -> {
        
                if (a[1] == b[1]) {
        
                    return a[0] - b[0];
                } else {
        
                    return b[1] - a[1];
                }
            });
    
            // 中间变量
            int total = 0; // 总用时
            int deploy = 0; // 部署所必须花费的时间
    
            // 参数初始化
            int[] dp = new int[n]; // 动态规划、执行完当前机器用时累计、因为不能同时部署2台机器所以可以使用动态规划
    
            for (int i = 0; i < n; i++) {
        
                // 状态转移方程
                dp[i] = deploy + machines[i][0] + machines[i][1]; // 执行完当前机器用时累计
                total = Math.max(dp[i], total); // 当前机器用时、已知累计时间最久的时间相比，取运行时间长的
                deploy += machines[i][0]; // 收集当前机器部署完成所用的时间，为下台机器用时统计做准备
            }
            return total;
        }
    }

**解题思路：**  
首先明确一点： 题中要求总耗时最短，而且注意到题中：每次只能配置一台机器，那么一个简单道理就是让任务工作时间最长的机器先运行；  
至于为什么，最浅显的解释是：如果让任务工作时间最短的在前面运行，那么同段时间的时间利用率就不是最高，因此并行数量越多越好，这样才会获得总体最短时间；

[Link 1]: https://leetcode-cn.com/circle/discuss/EC2mv8/view/zT3KcL/
[5ca6c222f1904f0abdda833607eeb9d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bcd0f5e2a55547b5b7e455ef4036429e.png