python - 使用Python在列表中进行计划优化[间隔计划]

在python中做一些学习问题，我遇到了一个很难解决的挑战。
需求
我有一个列表，其中第一项和最后一项分别是会议的开始时间和结束时间。
“可能的会议”是指会议1和2的开始时间和结束时间可以相同，或者1[[0,1][1,2][2,3],[2,5]]有三种可能的会议，因为第一次、第二次和第三次会议都可以按顺序进行，但最后一次会议不能——或者至少如果最后一次会议可以，第三次会议不能。
我需要返回可能的会议次数
没有任何关于适当算法的特殊知识，在这里可以很好地工作（仍在学习），我的方法是对列表进行排序，并将它们与下一个列表进行比较，看是否有可能召开会议。所有给定的问题集合都至少有一个可能发生的会议（因为至少有一个会议是可能的）。
下面是我在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

问题：
我觉得这是一种野蛮的分类和比较方法
我认为它的规模不大
有可能的情况会打破它
任何帮助在此将不胜感激！希望能扩展我对这类问题的理解。谢谢！

最佳答案

区间调度优化是一个标准问题，其贪婪算法在wikipedia中描述：
下面的贪心算法确实找到了最优解：
选择最早完成时间的间隔x
从候选间隔集中删除x和与x相交的所有间隔。
继续，直到候选间隔集为空。
目前的解决方案只需要O（nlogn）进行排序，再加上O（n）循环操作，因此是一种非常有效的方法，应该可以很好地扩展。
然而，这并不完全正确，因为：
按开始时间排序，而不是按结束时间排序
你比较每一个连续的会议
您可以使用以下代码修复这些问题：

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)

关于python - 使用Python在列表中进行计划优化[间隔计划]，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27449948/