python - 列表列表的 Python 调度优化 [间隔调度]

Question

在 python 中做一些学习问题，我遇到了一个我无法解决的挑战。

请求

• 我有一个列表列表，其中第一项和最后一项分别是 session 的开始时间和结束时间。

• “可能的 session ”是指 session 1 和 session 2 的开始和结束时间可以相同，或者 1 < 2，但不能重叠。所以在: [[0,1][1,2][2,3],[2,5]] 有 3 次可能的 session ，因为第 1、2、3 次 session 都可以按顺序发生，但是最后一个不能——或者至少如果最后一个可以发生，第三个不能。

• 我需要返回可能的 session 数量

• 没有任何关于在这里可以很好地工作的适当算法的特殊知识(仍在学习)，我的方法是对列表列表进行排序并将它们与下一个列表进行比较以查看 session 是否是可能的。该问题的所有给定集合至少有 1 次会面(因为至少有一次会面必然是可能的)。

这是我目前在 python3.4 中的内容:

def answer(meetings):
    index = 0
    nextIndex = index + 1
    possibleMeetings = 1
    impossibleMeetings = 0
    sortedMeetings = sorted(meetings)

    for item in sortedMeetings:
        firstItem = item[1]
        secondItem = sortedMeetings[nextIndex][0]

        if firstItem <= secondItem:
             possibleMeetings +=1
             nextIndex+=1
         elif firstItem > secondItem:
             impossibleMeetings +=1
             nextIndex+=1
        if nextIndex == len(sortedMeetings):
            break
    index +=1
return possibleMeetings, impossibleMeetings

问题:

• 我觉得这是一种对事物进行排序和比较的蛮力方式

• 我认为它不会很好地扩展

• 有可能会打破它

如有任何帮助，我们将不胜感激!希望扩展我对这类问题的可能性的概念。谢谢!

Answer 1

间隔调度优化是 wikipedia 中描述的贪心算法的标准问题。 :

The following greedy algorithm does find the optimal solution:

1. Select the interval, x, with the earliest finishing time.

2. Remove x, and all intervals intersecting x, from the set of candidate intervals.

3. Continue until the set of candidate intervals is empty.

您当前的解决方案只需要 O(nlogn) 的排序时间，加上 O(n) 的循环操作，因此是一种非常有效的方法，应该可以很好地扩展。

但是，这并不完全正确，因为:

1. 您按开始时间排序，而不是结束时间
2. 你比较每一对连续的 session

您可以使用以下代码解决这些问题:

def answer(meetings):
    last_end = -1
    ans = 0
    for end,start in sorted( (end,start) for start,end in meetings ):
        if start >= last_end:
            last_end = end
            ans += 1
    return ans, (len(meetings) - ans)