扫描线

一旦是这种区间问题, 要想到「扫描线」

0X00 模板题目

• 252. Meeting Rooms

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

• 253. Meeting Rooms II

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 注意事项

• 扫描线的排序问题

0X02 相关题目

• 252. Meeting Rooms

• 253. Meeting Rooms II

• 1229. Meeting Scheduler

• 218. The Skyline Problem