参加会议的最大数目

会议开始时间大于结束时间代表的是什么意思呀？这里为什么不能只关心会议的结束时间，排序后卡着会议的最后一天参加会议呢？

# -*- coding: utf-8 -*-

import heapq


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param meetings int整型二维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4d3151698e33454f98bce1284e553651?tpId=196&tqId=40523&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/solution/zui-duo-ke-yi-can-jia-de-hui-yi-shu-mu-by-leetcode/
        大神：老汤
    算法：
        本题使用贪心的策略：
            对于开始时间相同的会议，我们优先选择结束时间较早的会议先参加，这样才能保证参加更多的会议。比如会议列表为[[1, 1][1, 2], [1, 3], [1, 4]]，参加顺序为[1,1] -> [1,2] -> [1,3] -> [1,4]，这样恰好能在4天时间参加4个会议，达到最大化。
        1. 对于会议列表按开始时间进行升序排序
        2. 使用curDay表示当前是哪一天，使用小顶堆维护会议的结束时间，从第1天开始，我们将meetings[i][0] == curDay的会议时间，加入小顶堆。
        3. 将小顶堆中结束时间小于curDay的会议删除，这些会议都是过期的，无法参见了。
        4. 如果小顶堆不空，弹出堆顶元素，可参加会议数+1
        5. curDay += 1
    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
    """

    def attendmeetings(self, meetings):
        # write code here
        meetings.sort(key=lambda x: x[0])
        print meetings

        n = len(meetings)
        res, i, curDay, minHeap = 0, 0, 1, []
        while i < n&nbs***bsp;minHeap:
            while i < n and meetings[i][0] == curDay:  # 将所有开始时间等于curDay的会议结束时间加入minHeap
                heapq.heappush(minHeap, meetings[i][1])
                i += 1

            while minHeap and minHeap[0] < curDay:  # 将所有结束时间小于curDay的过期会议删除
                heapq.heappop(minHeap)

            if minHeap:  # 选择结束时间最早的会议进行参加
                heapq.heappop(minHeap)
                res += 1

            curDay += 1  # 日期+1

        return res


if __name__ == "__main__":
    sol = Solution()

    # matrix = [[1, 2], [2, 3], [4, 5]]

    # matrix = [[1, 2], [2, 3], [2, 3]]

    # matrix = [[5, 9], [16, 8], [6, 40], [17, 50], [13, 19], [15, 7], [21, 32], [10, 3], [1, 2], [27, 18]]

    matrix = [[8, 22], [16, 6], [5, 10], [20, 3], [12, 2], [18, 1], [36, 41], [17, 19], [46, 15], [38, 48], [25, 45],
              [35, 9]]

    res = sol.attendmeetings(matrix)

    print res