找到最大的非重叠

Question

我有一个任务列表[[5, 9], [1, 2], [3, 4], [0, 6], [5, 7], [8, 9]]。每个子列表有两个时间间隔。（例如：[5，9]，其中5是开始时间，9是结束时间）。我想得到一个列表，其中有最大的次数，不重叠。例如，在这种情况下：[1, 2],[3, 4],[5, 7],[8, 9]是最好的计划。在

我写了一个python程序，如果从一个间隔开始，它应该找出其他间隔的组合。 例如，如果我以[5,9]开头，它必须返回所有可能的组合。然后我可以一个接一个地输入所有的间隔，然后选择最大的输出。在

但是我的代码没有给出预期的输出。请帮我找出密码有什么问题。在

def findMax (tasks):
    maxCount = []
    maxTask = []
    for i in range (len (tasks)):
        if maxTask == []: maxTask.append (tasks [i])
        else:
            count = 0
            for j in range (len (maxTask)):
                if tasks [i] == maxTask [j]: continue
                else:
                    if (tasks [i][0] < maxTask [j][0] and tasks [i][1] <= maxTask [j][0]) or (tasks [i][0] >= maxTask [j][1] and tasks [i][1] > maxTask [j][0]): count += 1
                    if count == len (maxTask): maxTask.append (tasks [i])
        maxCount.append (len (maxTask))
        maxTask = []
    return max (maxCount)

Answer 1

您可以使用一个函数，该函数递归地遍历与现有可行任务列表不重叠的所有剩余任务，并在剩余任务中没有与任何可行任务重叠的任务时生成可行任务：

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

因此：

^{pr2}$

返回：[[1, 2], [3, 4], [5, 7], [8, 9]]

Answer 2

试试这个代码，对我有用：

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]]))

上一个任务2和下一个任务之间的差异是[1和下一个任务的[1和2]之间的差异是[1和2]之间的[1和2]之间的差异。然后它接受两个差异之和最小的任务。这可能不会总是给你正确的名单，但几乎。在

希望对你有帮助！在