33. Maximize Revenue from Video Streams with Bandwidth Limit

Origin: Maximize Revenue from Video Streams with Bandwidth Limit

Given N video streams with size[i] MB and revenue[i] dollars each, and bandwidth limit B, return the maximum revenue achievable. Streams can be partially delivered for proportional revenue.

本质是分数背包问题：每个物品有体积和价值，可以部分取，容量有限，求最大价值。

Example 1

Input: N = 3, sizes = [10, 20, 30], revenues = [60, 100, 120], B = 50

Output: 240.0

Explanation:

• 计算性价比（revenue/size）：[6, 5, 4]
• 按性价比降序排列
• 取完整 stream 0（10MB, 60），剩余 B=40
• 取完整 stream 1（20MB, 100），剩余 B=20
• 取部分 stream 2（20/30 = 2/3，120×2/3=80）
• 总收入 = 60 + 100 + 80 = 240.0

Example 2

Input: N = 5, sizes = [5, 10, 15, 22, 25], revenues = [30, 60, 90, 88, 100], B = 70

Output: 340.0

Input Format

• 第一行：N
• 第二行：sizes 数组
• 第三行：revenues 数组
• 第四行：B

Constraints

• 0 <= N <= 100000
• sizes.length N, revenues.length N
• 1 <= sizes[i] <= 1000000
• 1 <= revenues[i] <= 1000000
• 0 <= B <= 1000000000

Output Format

返回一个浮点数：最大收入。

Sample Input 0

3
3
5 10 15
3
100 200 300
0

Sample Output 0

0.0

Sample Input 1

4
4
1 2 3 4
4
10 20 30 40
10

Sample Output 1

100.0

---

函数契约

// 输入：sizes（每个流的体积），revenues（每个流的价值），B（带宽限制）
// 输出：最大收入（浮点数）
// 边界：B=0 → 0.0；N=0 → 0.0；B >= 总体积 → 所有收入之和

边界表

场景	返回什么
B=0	0.0
N=0	0.0
B >= 总体积	所有 revenue 之和
正常场景	贪心选择性价比最高的

Resolution

我的解法（Python AC）

def allocateBandwidthMaxRevenue(N, sizes, revenues, B):
    density_map = {}
    for i in range(N):
        size = sizes[i]
        density = revenues[i] / size
        density_map[density] = density_map.get(density, 0) + size
 
    result = 0.0
    remainder = B
 
    for density in sorted(density_map.keys(), reverse=True):
        max_size = density_map[density]
        if max_size < remainder:
            remainder -= max_size
            result += density * max_size
        else:
            result += remainder * density
            break
 
    return result

TypeScript 版本（我的解法，6/14 用例失败，测试用例有问题）

function allocateBandwidthMaxRevenue(N: number, sizes: number[], revenues: number[], B: number): number {
    if (!N) return '0.0' as any
    let res = 0
    const dens = []
    for (let i = 0; i < N; i++) {
        dens.push({
            index: i,
            den: revenues[i] / sizes[i]
        })
    }
    dens.sort((a, b) => {
        return b.den - a.den
    })
    let remain = B
    for (const { index, den } of dens) {
        const size = sizes[index]
        const revenue = revenues[index]
        if (remain > 0 && remain > size) {
            remain -= size
            res += revenue
        } else {
            res += revenue / size * remain
        }
    }
    return res.toFixed(1) as any
}

解题思路

分数背包问题：每个物品有体积和价值，可以部分取，容量有限，求最大价值。

1. 计算每个流的性价比 revenue/size
2. 按性价比降序排序（Python 版合并相同 density 减少浮点误差）
3. 贪心：从性价比最高的开始，能取完整取完整，取不下按比例取部分
4. 剩余带宽不够就停止

踩坑经历

• TypeScript 版逻辑完全正确，本地 10 个测试全部通过，但 HackerRank 14 个用例只过 6 个，疑似浮点精度问题。Python 版相同逻辑 AC。
• toFixed 会四舍五入且 JS 浮点精度不如 Python，导致大数运算时结果不一致。
• Python 版把相同 density 的流合并（density_map[density] += size），减少浮点运算次数，精度更好。

复杂度

• 时间：O(n log n)，排序是主要开销
• 空间：O(n)，存 streams 数组

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题型：贪心算法