时间戳

首页 > 解决方案 > 这个面试问题的最佳解决方案

optimization - 这个面试问题的最佳解决方案

问题描述

谁能提供具有时间复杂度的最佳解决方案？非常感激！

确定运行预定视频流所需的带宽。
可能有成千上万个流，并且所有调度数据在开始时都是可用的。
可能存在没有流运行的时间间隔

输入

int startTime; //start time for the stream  
int duration; //how long the stream runs  
int bandwidth; // consumed bandwidth from start to end

输出：

list[int] totalBW; // bandwidth needed at every time instant

示例：
输入（列表可能未排序）

[ [0,2,10], [1,2,10], [2,1,20] ]

输出

[10, 20, 30]

解释

At time 0: only the first element needs bandwidth 10 =>  [10, ...]
At time 1: first two elements need bandwidth 10 + 10 => [10, 20, ...]
At time 2: the second and third element need bandwidth 10 + 20 => [10, 20, 30]

使用python的蛮力方法：

def solution(streams):
    _max = max(streams, key=lambda x: (x[0]+x[1]))
    _max_time = _max[0] + _max[1] 
    res = [0] * _max_time
        
    for s, d, bw in streams:
        for i in range(d):
            res[s+i] += bw
    return res

有没有更有效的方法？

标签： optimization

解决方案

有没有更有效的方法？

是的。

第一步是将原始数据转换为一组“在时间 = T，带宽变化 N”事件，按时间顺序排序，并通过合并同时发生的事件来简化。

对于您的示例，如果输入是，[ [0,2,10], [1,2,10], [2,1,20] ] 那么它将被分解为：

** [ [0,2,10] **
    At 0, bandwidth += 10 
    At 2, bandwidth += -10

** [1,2,10] **
    At 1, bandwidth += 10
    At 3, bandwidth += -10

** [2,1,20] **
    At 2, bandwidth += 20
    At 3, bandwidth += -20

..然后排序和简化（合并同时发生的事件 - 例如bandwidth += -10, bandwidth += 20成为一个单一的bandwidth += 10）以获得：

At 0, bandwidth += 10 
At 1, bandwidth += 10
At 2, bandwidth += 10
At 3, bandwidth += -30

从那里，从排序列表生成最终数组是一件简单的事情：

 10, 20, 30, 0

要理解为什么这样做更有效，想象一下如果以更高的精度（例如，可能是毫秒而不是秒）跟踪时间并且输入是[ [0,2000,10], [1000,2000,10], [2000,1000,20] ] 相反的会发生什么。对于我的方法，生成最终数组将成为一个具有 4 次迭代的外循环和一个可以是高度优化的memset()(C) 或rep stosd(80x86 程序集) 或np.full()(Python with NumPy) 的内循环；对于您的方法，外循环需要 30000 次迭代，其中内循环浪费大量时间重复线性搜索（对于外循环的大多数迭代）找到与外循环的上一次迭代相同的答案。

推荐阅读