[LeetCode 253] Meeting Rooms II 扫描线的应用(Python)

扫描线的思想很巧妙，适用于一些一维算法问题的解决。这些问题涉及具有头尾节点的排序问题，单纯的对节点排序并不能很好的解决问题。扫描线应用的简单例子如LeetCode 253

Given an array of meeting time intervals consisting of start and end times [[s1,e1], [s2,e2],…] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

将这三个区间在x轴上画出来，并用一条垂直于x轴的线作为扫描线从左至右扫描，会很容易得出答案，即与扫描线焦点的最大值即为所求。但是在程序中我们怎样表示这种思想呢？
-对所有点进行标记，区分起始点和终止点
-对所有点进行排序
-依次遍历每个点，遇到起始点+1，遇到终止点-1，并更新记录最大值

代码如下

# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e

class Solution:
def minMeetingRooms(self, 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])

        n = 0
        max_num = 0
for arr in tmp:
# 起始点+1
if arr[1]:
                n += 1
# 终止点-1
else:
                n -= 1
            max_num = max(n, max_num)
return max_num