作业任务调度——贪心选择(最少的机器数)给定n个任务的集合T，每个任务的开始时间s₁和结束时间fᵢᵢSᵢ满足ᵢᵢsᵢ<fᵢ°每个任务只能在一台机器上执行，每台机器同时只能执行一个任务。两个任务i和j不冲突iff：ⱼᵢfⱼ≤sᵢ或ᵢⱼfᵢ≅sⱼ求解：如何安排T中所有任务在不冲突时最少的机器上完成。[1,4],[1,3],[2,5],[3,7],[4,7],[6,9],[7,8]

这个问题可以使用贪心算法来求解。首先将所有任务按照结束时间从早到晚排序，然后依次将任务分配给空闲机器中结束时间最早的那台机器。如果没有空闲的机器，则开一台新机器。这样可以保证在不冲突的情况下，最少的机器数完成所有任务。对于给定的任务集合T，按照结束时间排序后，贪心算法的具体实现可以参考以下代码：

def schedule_tasks(tasks):
    machines = []  # 记录每台机器的结束时间
    for task in sorted(tasks, key=lambda x: x[1]):
        machine = None
        for i, end_time in enumerate(machines):
            if task[0] >= end_time:
                machine = i
                break
        if machine is None:
            machines.append(task[1])
        else:
            machines[machine] = task[1]
    return len(machines)
 
tasks = [(1,4),(1,3),(2,5),(3,7),(4,7),(6,9),(7,8)]
print(schedule_tasks(tasks))  # 输出结果为3

这个算法时间复杂度为O(nlogn)，其中n为任务的个数。

相关问题

作业任务调度——贪心选择（最少的机器数）python代码实现

以下是一个可能的贪心算法实现：

def schedule(tasks):
    # 将任务按照截止时间从早到晚排序
    tasks = sorted(tasks, key=lambda t: t[1])
    # 维护每个机器的完成时间
    machine_finish_time = [0]
    for task in tasks:
        # 在当前完成时间最早的机器中找一个能够完成该任务的机器
        min_finish_time = min(machine_finish_time)
        machine_index = machine_finish_time.index(min_finish_time)
        if min_finish_time >= task[0]:
            # 当前机器可以完成该任务，更新完成时间
            machine_finish_time[machine_index] = task[1]
        else:
            # 当前机器无法完成该任务，开启新机器并更新完成时间
            machine_finish_time.append(task[1])
    # 返回使用的机器数
    return len(machine_finish_time)

这个函数接受一个任务列表，每个任务由一个元组 `(start_time, end_time)` 表示。它会按照任务的截止时间顺序对任务进行排序，然后采用贪心思想，从当前完成时间最早的机器中选择一个尽可能早地完成任务，如果没有机器能够完成该任务，则开启一个新机器。最终返回使用的机器数。

需要注意的是，这个贪心算法并不一定总能得出最优解，但是在实际应用中效果通常都比较好。

n个任务,k个可以并行工作的机器,完成任务i的时间是ti,求最佳调度时间

这个问题可以用贪心算法来解决。具体步骤如下：

1. 将所有任务按照完成时间从小到大排序，完成时间越小的任务先执行。
2. 初始化一个长度为k的列表，用来存放每台机器完成任务的时间。将列表中的元素全部初始化为0。
3. 依次将每个任务分配给完成时间最早的机器，即将该任务分配给列表中时间最小的机器，并更新该机器的完成时间。
4. 重复步骤3，直到所有任务都被分配完毕。

最终的最佳调度时间为所有机器完成时间的最大值。

这个算法的时间复杂度为O(nlogn)，其中n为任务的数量，因为需要对任务进行排序。空间复杂度为O(k)，其中k为机器的数量，即需要一个列表来存放每台机器的完成时间。