当前位置: 面试刷题>> 任务调度器 (经典算法题500道)


题目描述补充

任务调度器是一个系统,用于管理一系列任务的执行顺序,确保没有两个相同的任务在连续的时间段内被执行,以此来平衡系统的负载并优化资源使用。给定一个任务列表(以任务名称的字符串数组形式给出),以及一个整数n,表示两个相同任务之间必须至少间隔n个时间单位(时间单位可以是任意单位,如秒、分钟等)。编写一个函数来重新排列这些任务,使得它们满足上述条件,并返回重新排列后的任务列表。如果无法重新排列以满足条件,则返回空列表。

示例输入

  • 任务列表:["A", "A", "A", "B", "B", "C"]
  • 间隔:2

示例输出

  • ["A", "B", "C", "A", "B", "A"]

在这个例子中,由于任务"A"之间至少需要间隔2个时间单位,因此我们将"A"分散在列表中,并在它们之间插入其他任务(如"B"和"C"),以满足间隔要求。

PHP 示例代码

function taskScheduler($tasks, $n) {
    $count = array_count_values($tasks); // 统计每个任务的出现次数
    $maxFreq = max($count); // 获取最高频率
    $slots = $maxFreq * ($n + 1); // 计算总时间槽数
    $schedule = array_fill(0, $slots, ''); // 初始化时间槽

    // 分配任务到时间槽
    foreach ($count as $task => $freq) {
        $interval = ($maxFreq - $freq) * ($n + 1) + 1; // 计算起始间隔
        for ($i = 0; $i < $freq; $i++) {
            $schedule[($i * ($n + 1)) % $slots + $interval] = $task;
        }
    }

    // 过滤掉空槽,得到最终的任务列表
    return array_filter($schedule);
}

// 示例用法
$tasks = ["A", "A", "A", "B", "B", "C"];
$n = 2;
$result = taskScheduler($tasks, $n);
print_r($result);

注意: PHP 示例中的 array_filter 调用实际上可能不直接返回题目期望的连续非空任务列表,因为 array_filter 会保留数组键。对于严格的任务列表顺序,可能需要额外的步骤来重新索引数组或使用其他逻辑来构建最终的任务列表。

Python 示例代码

def taskScheduler(tasks, n):
    from collections import Counter
    count = Counter(tasks)
    max_freq = max(count.values())
    slots = [0] * (max_freq * (n + 1))
    
    for task, freq in count.items():
        interval = (max_freq - freq) * (n + 1)
        for i in range(freq):
            slots[(i * (n + 1) + interval) % len(slots)] = task
    
    # 过滤空槽并返回结果
    return [task for task in slots if task]

# 示例用法
tasks = ["A", "A", "A", "B", "B", "C"]
n = 2
result = taskScheduler(tasks, n)
print(result)

JavaScript 示例代码

function taskScheduler(tasks, n) {
    const count = {};
    for (let task of tasks) {
        count[task] = (count[task] || 0) + 1;
    }
    const maxFreq = Math.max(...Object.values(count));
    const slots = new Array(maxFreq * (n + 1)).fill('');
    
    for (let task in count) {
        let interval = (maxFreq - count[task]) * (n + 1);
        for (let i = 0; i < count[task]; i++) {
            slots[(i * (n + 1) + interval) % slots.length] = task;
            interval++;
            if (interval > n) interval = 1; // 防止间隔过大
        }
    }

    // 过滤空槽
    return slots.filter(task => task !== '');
}

// 示例用法
const tasks = ["A", "A", "A", "B", "B", "C"];
const n = 2;
const result = taskScheduler(tasks, n);
console.log(result);

码小课网站中有更多相关内容分享给大家学习,希望这些示例代码能帮助你理解任务调度器的实现方式。

推荐面试题