Meeting Rooms

题目描述

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example, Given [[0, 30],[5, 10],[15, 20]], return false.

解题方法

没有思路就先sort一下，这一题可以用comparator先根据起始时间sort一下, 这样后面的必然在前面之后开始，只需要考虑结束时间就可以。

然后我们再看怎样的情况下会有重叠的intervals，如果后面任意一个的start time早于前面的end time, 那么就代表重叠了。 我们需要比较后面的每一个吗？不需要，因为起始时间是有序的，只要后面第一个的start time晚于当前这一个的end time，就表示后面的肯定与当前这一个没有重叠。

所以我们Loop through每一个interval，比较intervals[i]的end time和intervals[i+1]的start time就可以。

comparator先把intervals按照start time sort一下

Solution

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

class Solution(object):
    def canAttendMeetings(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: bool
        """
        def compare(a, b):
            return a.start - b.start

        intervals = sorted(intervals, cmp=compare)

        length = len(intervals)
        if length == 1:
            return True

        for i in range(1, length):
            if intervals[i].start < intervals[i-1].end:
                return False
        return True

Reference