[LeetCode] 252. Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [start, end], determine if a person could attend all meetings.

Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:
Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= start < end <= 106

会议室 I。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/meeting-rooms
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 按会议开始时间排序

给的 input 是一个二维数组，二维数组里面的每一个元素记录了每个会议的开始时间和结束时间。问同一个人是否有可能参加所有的会议。思路很简单，这是LC上算是一种比较特别的题型 - 扫描线。这题的思路是按照会议开始时间给 input 排序，如果有任何一个会议的结束时间 > 下一个会议的开始时间，就 return false。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

JavaScript实现

/**
 * @param {number[][]} intervals
 * @return {boolean}
 */
var canAttendMeetings = function (intervals) {
	let sorted = intervals.sort((a, b) => a[0] - b[0]);
	for (let i = 1; i < sorted.length; i++) {
		if (sorted[i - 1][1] > sorted[i][0]) {
			return false;
		}
	}
	return true;
};

思路二 - 按结束时间排序

这道题也可以按照会议结束时间排序，然后从第二个会议开始看，如果有任何一个会议的开始时间早于前一个会议的结束时间，则 return false。思路跟 JS 的版本其实都是类似的，无非是实现方式稍有差异。

代码

Java实现

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

相关题目

252. Meeting Rooms
253. Meeting Rooms II
2406. Divide Intervals Into Minimum Number of Groups