MarsCode-小M的多任务下载器挑战

小M的多任务下载器挑战

问题描述

小M的程序设计大作业是编写一个多任务下载器。在实现过程中，他遇到了一个问题：在一次下载过程中，总共有N个任务，每个任务会在第x秒开始，并持续y秒。小M需要知道，在同一时刻，最多有多少个任务正在同时下载，也就是计算出任务的最高并发数。

• n 表示任务的数量。
• array 是一个二维列表，每个元素为[x, y]，表示任务的开始时间和持续时间，其中：
• x 表示任务的开始时间；
• y 表示任务的持续时间。

---

测试样例

样例1：

输入：n = 2 ,array = [[1, 2], [2, 3]]
输出：2

样例2：

输入：n = 4 ,array = [[1, 2], [2, 3], [3, 5], [4, 3]]
输出：3

样例3：

输入：n = 5 ,array = [[1, 3], [3, 4], [2, 2], [6, 5], [5, 3]]
输出：3

解答

思路一-遍历

先按起始时间排序，再遍历整个下载周期。时间复杂度高

def solution(n, array):
    # Edit your code here
    array.sort(key= lambda x: x[0])
    max_concurrency = 0
    end = 0
    for i in range(n):
        start_time = array[i][0]
        duration = array[i][1]
        end_time = start_time + duration
        array[i][1] = end_time # 将持续时间转为截至时间
        if end_time > end:
            end = end_time
    start = array[0][0]
    
    for time in range(start, end+1):
        concurrency = 0
        for i in range(n):
            if array[i][0] <= time < array[i][1]:
                concurrency += 1
        if concurrency > max_concurrency:
            max_concurrency = concurrency

    return max_concurrency

思路二-事件驱动

将每个任务的开始和结束时间视为事件，并使用事件驱动的方法来计算并发任务数。

时间复杂度O(n)

def solution(n, array):
    events = []
    
    # 将每个任务的开始和结束时间转换为事件
    for task in array:
        start_time = task[0]
        end_time = task[0] + task[1]
        events.append((start_time, 1))  # 开始事件
        events.append((end_time, -1))   # 结束事件
    
    # 按照时间顺序排序事件
    events.sort()
    
    max_concurrency = 0
    current_concurrency = 0
    
    # 遍历事件，计算并发任务数
    for event in events:
        current_concurrency += event[1]
        max_concurrency = max(max_concurrency, current_concurrency)
    
    return max_concurrency

if __name__ == "__main__":
    # Add your test cases here
    print(
        solution(2, [[1,2], [2,3]]) == 2
    )
    print(
        solution(4, [[1,2], [2,3],[3,5], [4,3]]) == 3
    )