leetcode 会议室系列

252. 会议室

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

示例 1：

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

示例 2：

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

思路

基于贪心。看看现在这个时间能不能去开会，能则时间置为结束时间。开下个会议时再看看能不能去开会，直到把整个列表的会开完，则返回 true，若中途结束时间大于开会时间则说明这个会议不能参加，则返回 false。

复杂度

时间复杂度：$O(NlogN)$，排序最少需要 $O(NlogN)$

空间复杂度：$O(1)$

代码

class Solution {
    public boolean canAttendMeetings(int[][] a) {
        Arrays.sort(a, (x, y) -> x[0] == y[0] ? x[1] - y[1] : x[0] - y[0]);
        int i = 0;
        for (int[] x : a) {
            if (i <= x[0]) i = x[1];
            else return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11

253. 会议室 II

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1：

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

示例 2：

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

思路

贪心策略。开会的时候先看看有没有结束的会议，如果有则复用，如果没有就新开一个会议室。

复杂度

时间复杂度：$O(NlogN)$，排序最少需要 $O(NlogN)$

空间复杂度：$O(N)$

代码

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int res = 0, n = intervals.length;
        
        int a[] = new int[n];
        int b[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = intervals[i][0];
            b[i] = intervals[i][1];
        }

        Arrays.sort(a);
        Arrays.sort(b);

        for (int i = 0, j = 0; i < n; i++) {
            if (a[i] < b[j]) res++;
            else j++;
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22