扫描线
2020-03-12 本文已影响0人
madao756
一旦是这种区间问题, 要想到「扫描线」
0X00 模板题目
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
# 最后记得检查边界
points = []
for start, end in intervals:
points.append((start, True))
points.append((end, False))
points.sort()
count = 0
for i in range(len(points)):
time, flag = points[i]
if flag:
count += 1
if count > 1: return False
else:
count -= 1
return True
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
# 注意检查边界
# end 在 start 前
sweep = []
for start, end in intervals:
sweep.append((start, True))
sweep.append((end, False))
sweep.sort()
count = 0
ans = 0
for time, flag in sweep:
if flag:
count += 1
ans = max(ans, count)
else:
count -= 1
return ans
0X01 注意事项
扫描线的排序问题
