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

请多多指教。

文章标题:920. Meeting Rooms

本文作者:顺强

发布时间:2020-04-27, 23:59:00

原始链接:http://shunqiang.ml/leetcode-920-meeting-rooms/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏