920. Meeting Rooms

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

Have you met this question in a real interview?

Example
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

解题思路：
大致和 Merge Intervals 思考一致，首先进行排序后，然后判断相邻元素之间是否存在冲突，即比较前一个元素的 end 和后一个元素的 start .

注意：
Interval 操作与数组不同

"""
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
        # print(intervals[0].lower)
        # print(1)
        self.quicksort(intervals, 0,len(intervals)-1)
        # print(interval)
        for i in range(len(intervals)):
            if i < len(intervals)-1 and intervals[i].end > intervals[i+1].start:
                return False
        return True

    def quicksort(self,nums,l,h):
        if l < h:
            pivotpos = self.partition(nums,l,h)
            self.quicksort(nums,l,pivotpos - 1)
            self.quicksort(nums,pivotpos + 1,h)

    def partition(self,nums,l,h):
        p = nums[l]
        while l < h:
            while l < h and nums[h].start >= p.start:
                h -= 1
            nums[l] = nums[h]
            while l < h and nums[l].start <= p.start:
                l += 1
            nums[h] = nums[l]
        nums[l] = p
        return l