找到最大的非重叠区间

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):&nbsp; &nbsp; if not viable_tasks:&nbsp; &nbsp; &nbsp; &nbsp; viable_tasks = []&nbsp; &nbsp; &nbsp; &nbsp; tasks = sorted(tasks)&nbsp; &nbsp; found_viable = False&nbsp; &nbsp; for i, (start, end) in enumerate(tasks):&nbsp; &nbsp; &nbsp; &nbsp; for viable_start, viable_end in viable_tasks:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if viable_start < start < viable_end or viable_start < end < viable_end or start < viable_start < end or start < viable_end < end:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; found_viable = True&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield from schedule(tasks[:i] + tasks[i + 1:], viable_tasks + [[start, end]])&nbsp; &nbsp; if not found_viable:&nbsp; &nbsp; &nbsp; &nbsp; 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]]

Answer 2

试试这个代码，它对我有用：def getCombi(tasks):&nbsp; &nbsp; first = getNext([0,0], tasks)&nbsp; &nbsp; combi = [first]&nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp; nextTask = getNext(combi[-1],tasks)&nbsp; &nbsp; &nbsp; &nbsp; if nextTask != ["EmptyTask"]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combi.append(nextTask)&nbsp; &nbsp; &nbsp; &nbsp; else: break&nbsp; &nbsp; return combidef getNext(MainTask, tasks):&nbsp; &nbsp; i = MainTask[1]&nbsp; &nbsp; taskDiffrencesList = []&nbsp; &nbsp; for task in tasks:&nbsp; &nbsp; &nbsp; &nbsp; if task[0] > i:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x = task[0]-i&nbsp; &nbsp; &nbsp; &nbsp; else: continue&nbsp; &nbsp; &nbsp; &nbsp; d = task[1]-task[0]&nbsp; &nbsp; &nbsp; &nbsp; taskDiffrencesList.append([[x,d],task])&nbsp; &nbsp; smallestDiffrence = [10000, ["EmptyTask"]]&nbsp; &nbsp; for entry in taskDiffrencesList:&nbsp; &nbsp; &nbsp; &nbsp; if entry[0][0]+entry[0][1] < smallestDiffrence[0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; smallestDiffrence[0] = entry[0][0]+entry[0][1]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; smallestDiffrence[1] = entry[1]&nbsp; &nbsp; 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] 之间）。然后它执行两个差值总和最小的任务。这可能不会总是给你正确的列表，但几乎。