920 · 会议室 - LintCode

Difficulty
easy
Tags
扫描线
URL
https://www.lintcode.com/problem/920/
Star
给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。
Example1
Input: intervals = [(0,30),(5,10),(15,20)]
Output: false
Explanation:
(0,30), (5,10) and (0,30),(15,20) will conflict
Example2
Input: intervals = [(5,8),(9,15)]
Output: true
Explanation:
Two times will not conflict

法1 扫描线

思路
经典的扫描线题目。按照套路：
  1. 先将区间按照开始、结束划分开
  1. 对划分好的时间点按时间进行排序，如果时间相同，则截止拍在开始前面
  1. 遍历时间点，看是否有重复时间段
题解
"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: if a person could attend all meetings
    """
    def canAttendMeetings(self, intervals):
        # Write your code here
        points = []
        for i in range(len(intervals)):
            points.append([intervals[i].start, 1])
            points.append([intervals[i].end, -1])

        points.sort(key=lambda x:(x[0], x[1]))

        count = 0
        for point in points:
            count += point[1]
            if count > 1:
                return False
        return True