[leetcode/lintcode 题解] 阿里算法面试真题:高效作业处理服务

简介: [leetcode/lintcode 题解] 阿里算法面试真题:高效作业处理服务

描述
Twitter正在测试一种名为Pigeon的新工作处理服务。
Pigeon处理任何任务的时间是任务实际持续时间的两倍,并且每个任务都有一个权重。 此外,Pigeon在一个小时内只能服务一个有限的持续时间(最大运行时间)。
给定Pigon服务的最大运行时间,任务的实际运行时间和权重,确定Pigon服务在一小时内可以实现的最大总权重。
输入包括以下参数:

  • n: 任务数量
  • weights: 每个任务的权重
  • tasks: 每个任务实际持续时间
  • p: Pigeon一小时的最大运行时间
  • 1≤n≤10^3
  • 1≤weights[i]≤10^6
  • 1≤tasks[i]≤100
  • 1≤p≤10^3

每个任务只能被执行一次。

在线评测地址:领扣题库官网

样例1
输入:
4
[2,4,4,5]
[2,2,3,4]
15
输出: 
10
说明:
你可以运行0、1、2号任务,将花费2 * (2 + 2 + 3) = 14 分钟并获得 2 + 4 + 4 = 10 权重。
样例2
输入:
3
[3,2,2]
[3,2,2]
9
输出: 
4
说明:
你可以运行1、2号任务,将花费2 * (2 + 2) = 8 分钟并获得 2 + 2 = 4 权重。

考虑01背包进行求解,将p除2是总容量,每个人物的时间是他需要的容量,价值为权重
代码

public class Solution {
    /**
     * @param n: the number of tasks
     * @param weights: the weight for every task
     * @param tasks: the actual duration of every task
     * @param p: maximum runtime for Pigeon in an hour
     * @return: the maximum total weight that the Pigeon service can achieve in an hour
     */
    public int maxWeight(int n, int[] weights, int[] tasks, int p) {
        // write your code here
        int[][] dp = new int[n + 1][p / 2 + 1];     
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= p / 2; j++) {
                if (j < tasks[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tasks[i - 1]] + weights[i - 1]);
                }
            }
        }

        return dp[n][p / 2];
    }
}

更多题解参考:九章官网solution

相关文章
|
3天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
3天前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
3天前
|
存储 算法 数据可视化
如何使用多种算法解决LeetCode第135题——分发糖果问题
如何使用多种算法解决LeetCode第135题——分发糖果问题
|
3天前
|
算法 数据可视化 数据挖掘
最佳加油站选择算法:解决环路加油问题的两种高效方法|LeetCode力扣134
最佳加油站选择算法:解决环路加油问题的两种高效方法|LeetCode力扣134
|
3天前
|
存储 SQL 算法
LeetCode题目112:多种算法实现路径总与改进过程
LeetCode题目112:多种算法实现路径总与改进过程
|
3天前
|
存储 缓存 算法
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
|
8天前
|
存储 算法 Java
JAVA后端开发面试题库
JAVA后端开发面试题库
16 1
|
12天前
|
缓存 安全 Java
【Java面试——并发基础、并发关键字】
随着硬件指令集的发展,我们可以使用基于冲突检测的乐观并发策略: 先进行操作,如果没有其它线程争用共享数据,那操作就成功了,否则采取补偿措施(不断地重试,直到成功为止)。这种乐观的并发策略的许多实现都不需要将线程阻塞,因此这种同步操作称为非阻塞同步。 乐观锁需要操作和冲突检测这两个步骤具备原子性,这里就不能再使用互斥同步来保证了,只能靠硬件来完成。硬件支持的原子性操作最典型的是: 比较并交换(Compare-and-Swap,CAS)。CAS 指令需要有 3 个操作数,分别是内存地址 V、旧的预期值 A 和新值 B。当执行操作时,只有当 V 的值等于 A,才将 V 的值更新为 B。
|
21天前
|
SQL 存储 Java
致远互联java实习生面试
致远互联java实习生面试
32 0
|
21天前
|
Java
java面试基础 -- 普通类 & 抽象类 & 接口
java面试基础 -- 普通类 & 抽象类 & 接口
24 0