題目出處

920 · Meeting Rooms

難度

easy

個人範例程式碼

from typing import (
    List,
)
from lintcode import (
    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 can_attend_meetings(self, intervals: List[Interval]) -> bool:
        # Write your code here
        if not intervals:
            return True

        intervals.sort(key = lambda x:x.start)
        end = intervals[0].end
        for i, interval in enumerate(intervals):
            if i > 0:
                if end <= interval.start: # end <= next_start (0,8), (8,10)
                    end = interval.end
                    continue
                else:
                    return False

        return True

算法說明

單純檢查會議室有沒有重疊時間的問題，我們可以先 sort start 時間後，
再檢查是否「上一個 end <= 下一個 start 」的時間點
(題目有說，(0, 8),(8, 10)不算是共用會議室，因此要有「等於」)

當我們發現不符合我們上述的規則時，
直接 return False。

input handling

如果沒有 intervals, 回傳 True (題目沒特別要求)

Boundary conditions

用 for 迴圈控制範圍

Reference

• 会议室 · Meeting Rooms