为了账号安全,请及时绑定邮箱和手机立即绑定

找到最大的非重叠区间

找到最大的非重叠区间

慕哥9229398 2021-07-09 16:00:31
我有一个任务清单[[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)
查看完整描述

2 回答

?
Smart猫小萌

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


查看完整回答
反对 回复 2021-07-27
?
qq_花开花谢_0

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] 之间)。然后它执行两个差值总和最小的任务。这可能不会总是给你正确的列表,但几乎。


查看完整回答
反对 回复 2021-07-27
  • 2 回答
  • 0 关注
  • 278 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信