2 回答
TA贡献1911条经验 获得超7个赞
您可以使用一个函数递归遍历所有与现有可行任务列表不重叠的剩余任务,并在剩余任务中没有更多任务与任何不重叠的任务时产生可行任务可行的任务:
def schedule(tasks, viable_tasks=None):
if not viable_tasks:
viable_tasks = []
tasks = sorted(tasks)
found_viable = False
for i, (start, end) in enumerate(tasks):
for viable_start, viable_end in viable_tasks:
if viable_start < start < viable_end or viable_start < end < viable_end or start < viable_start < end or start < viable_end < end:
break
else:
found_viable = True
yield from schedule(tasks[:i] + tasks[i + 1:], viable_tasks + [[start, end]])
if not found_viable:
yield viable_tasks
以便:
tasks = [[5, 9], [1, 2], [3, 4], [0, 6], [5, 7], [8, 9]]
max(schedule(tasks), key=len))
返回: [[1, 2], [3, 4], [5, 7], [8, 9]]
TA贡献1835条经验 获得超7个赞
试试这个代码,它对我有用:
def getCombi(tasks):
first = getNext([0,0], tasks)
combi = [first]
while True:
nextTask = getNext(combi[-1],tasks)
if nextTask != ["EmptyTask"]:
combi.append(nextTask)
else: break
return combi
def getNext(MainTask, tasks):
i = MainTask[1]
taskDiffrencesList = []
for task in tasks:
if task[0] > i:
x = task[0]-i
else: continue
d = task[1]-task[0]
taskDiffrencesList.append([[x,d],task])
smallestDiffrence = [10000, ["EmptyTask"]]
for entry in taskDiffrencesList:
if entry[0][0]+entry[0][1] < smallestDiffrence[0]:
smallestDiffrence[0] = entry[0][0]+entry[0][1]
smallestDiffrence[1] = entry[1]
return smallestDiffrence[1]
print(getCombi([[5,9],[1,2],[3,4],[0,6],[5,7],[8,9]]))
因此,有一个循环根据与前一个数字的差异以及下一个任务的数字之间的差异寻找最佳的下一个任务,例如,如果前一个任务是 task1 = [3,5] 而另一个是 task2 = [7,10] 差异是 2(在 task1[1] 和 task2[0] 之间)和 3(在 task2[0] 和 task2[1] 之间)。然后它执行两个差值总和最小的任务。这可能不会总是给你正确的列表,但几乎。
添加回答
举报