Python中列表的调度优化[interval scheduling]

Question

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

需求

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

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

• 我需要返回可能的会议次数

• 我的方法是对列表进行排序，并将它们与下一个列表进行比较，看看是否有可能召开会议。问题的所有给定集合至少有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. 你比较每一对连续的会议

您可以使用以下代码修复这些问题：

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)