LeetCode253 会议室 II

发表于 | 分类于 |
字数统计: 497 | 阅读时长 ≈ 2

链接: https://leetcode-cn.com/problems/meeting-rooms-ii/

题意

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回所需会议室的最小数量 。

解法

将会议时间按开始时间由小到大进行排序，对于这个问题
我们可以考虑对于每一个会议，需要安排一个会议室
那显然是找一个结束最早的会议，看看当前会议的开始时前一个会议是否结束
所以可以维护一个优先队列，每次取堆顶看看是否小于当前会议的开始时间

另一个解法是可以将这个问题视作公交上车问题

1
2
↑    ↑    ↓     ↑      ↓             ↓
0----5----10----15-----20-----------30-->

用一个map存储每个时间段的上车和下车情况，然后从前往后遍历，找出人数最多的时刻即为最多所需要的会议室数量

代码

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    static bool cmp(vector<int>& pa, vector<int>& pb) {
        if (pa[0] == pb[0]) return pa[1] < pb[1];
        return pa[0] < pb[0];
    }
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = intervals.size();
        int ans = 0;
        sort(intervals.begin(), intervals.end(), cmp);
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < n; i++) {
            if (pq.empty()) {
                pq.push(intervals[i][1]);
                ans++;
            }
            else if (intervals[i][0] < pq.top()) {
                // cout << pq.top() << endl;
                ans++;
                pq.push(intervals[i][1]);
            }
            else {
                pq.pop();
                pq.push(intervals[i][1]);
            }
        }
        return ans;
    }
};

上下车算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    static bool cmp(vector<int>& pa, vector<int>& pb) {
        if (pa[0] == pb[0]) return pa[1] < pb[1];
        return pa[0] < pb[0];
    }
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = intervals.size();
        int ans = 0, temp = 0;
        map<int, int> mp;
        for (int i = 0; i < n; i++) {
            mp[intervals[i][0]]++;
            mp[intervals[i][1]]--;
        }
        for (auto [k, v]: mp) {
            temp += v;
            ans = max(ans, temp);
        }
        return ans;
    }
};