252. 会议室

252. 会议室 #

链接 #

题目 #

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：false

示例 2：

输入：intervals = [[7,10],[2,4]]
输出：true

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106

解答 #

本质上就是判断是否存在交叉。

var canAttendMeetings = function(intervals) {
    if (intervals.length === 0) {
        return true;
    }

    intervals.sort((a, b) => a[0] - b[0]);

    for (let i = 0; i < intervals.length - 1; i++) {
        if (intervals[i][1] > intervals[i + 1][0]) {
            return false;
        }
    }
    return true;
};

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort()
        for i in range(len(intervals) - 1):
            if intervals[i][1] > intervals[i+1][0]:
                return False

        return True

也可以用扫描线算法实现。排序后，扫描线从左到右扫描，当遇到一个会议的开始时间时，计数器加一，遇到一个会议的结束时间时，计数器减一。如果计数器在任何时刻大于 1，说明有会议重叠，返回 false。

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        events = []
        for start, end in intervals:
            events.append((start, 1))
            events.append((end, -1))
        events.sort()
        cnt = 0
        for _, delta in events:
            cnt += delta
            if cnt > 1:
                return False
        return True