难度: Easy
Submission
运行时间: 23 ms
内存: 18.1 MB
class Solution: def canAttendMeetings(self, intervals: List[List[int]]) -> bool: intervals.sort(key= lambda x:x[0]) for i in range(len(intervals)-1): if intervals[i][1] > intervals[i+1][0]: return False return True
Explain
这个题解的思路是先将区间按照开始时间进行排序,然后遍历排序后的区间列表,检查相邻两个区间是否存在重叠。如果某两个相邻区间的结束时间大于下一个区间的开始时间,说明存在重叠,返回 False。如果遍历完整个列表都没有发现重叠,则返回 True,表示可以参加所有会议。
时间复杂度: O(nlogn)
空间复杂度: O(1)
class Solution: def canAttendMeetings(self, intervals: List[List[int]]) -> bool: # 按照区间的开始时间对区间列表进行排序 intervals.sort(key= lambda x:x[0]) # 遍历排序后的区间列表 for i in range(len(intervals)-1): # 检查相邻两个区间是否存在重叠 if intervals[i][1] > intervals[i+1][0]: # 如果存在重叠,返回 False return False # 如果遍历完整个列表都没有发现重叠,返回 True return True
Explore
是的,这种方法仍然有效。算法首先按照会议的开始时间对会议进行排序。这样做的目的是为了确保任何可能的重叠都会在相邻的会议之间出现。然后,算法遍历排序后的会议列表,比较当前会议的结束时间与下一个会议的开始时间。如果任何一个会议的结束时间大于下一个会议的开始时间,就意味着存在重叠。这种检查方式不仅适用于两个相邻的会议,也有效地处理了多个连续会议重叠的情况,因为每一对相邻会议都会被检查。
在这个算法中,如果会议列表为空(即没有会议),或者只有一个会议,算法都会返回 True。这是因为在这两种情况下,不存在任何相邻的会议对来检查重叠。具体来说,如果会议列表为空,算法中的 for 循环不会执行,因为它是基于列表长度的(len(intervals)-1 会小于 0),所以直接返回 True。如果列表中只有一个会议,同样因为没有相邻的会议对,for 循环也不会执行,因此也会返回 True。这样处理是符合逻辑的,因为没有会议或只有一个会议时,自然不会有重叠问题。