欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 253. 会议室 II

程序员文章站 2022-06-03 09:57:35
...

LeetCode 253. 会议室 II

方法一:前缀和算法

思路:利用前缀和算法,对每个interval开始位置+1,结束位置-1,然后做数组前缀和,答案是前缀和最大值。

class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {       
        map<int, int>m;
        for (auto x : intervals) {//对每个interval开始位置+1,结束位置-1
            ++m[x.start]; --m[x.end];
        }
        int rooms = 0, ans = 0;
        for (auto it : m)//做数组前缀和
            ans = max(ans, rooms += it.second);
        return ans;
    }
};
相关标签: LeetCode