CodeCollection2018
8/21/2019 - 3:10 PM

leetCode--Meeting Rooms II

给定代表各个会议起始和结束时间的时间段，其中可能会有重叠，为最少安排多少会议室能够安排下这些会议。 采用的方法具有通用性：扫描线方法。扫描线的思想很巧妙，适用于一些一维算法问题的解决。这些问题涉及具有头尾节点的排序问题。 例如[[0, 30],[5, 10],[15, 20]]，将这三个区间在x轴上画出来，并用一条垂直于x轴的线作为扫描线从左至右扫描，会很容易得出答案，即与扫描线焦点的最大值即为所求。但是在程序中我们怎样表示这种思想呢？ -对所有点进行标记，区分起始点和终止点 -对所有点进行排序 -依次遍历每个点，遇到起始点+1，遇到终止点-1，并更新记录最大值

meeting rooms II
content_copyfile_download
def minMeetingRoom(intervals):
    if intervals is None or len(intervals)==0:
        return 0
    tmp = []
    for inter in intervals:
        tmp.append((inter.start,True))
        tmp.append((inter.end,False))
    
    tmp = sorted(tmp,key=lambda v:(v[0],v[1]))

    n=0
    max_num=0
    for arr in tmp:
        if arr[1]:
            n+=1
        else:
            n-=1
        max_num = max(max_num,n)
    return max_num