力扣2406.将区间分为最少组数

力扣2406.将区间分为最少组数

小根堆法

• 用一个小根堆储存每一组的右端点

•   class Solution {
    public:
        int minGroups(vector<vector<int>>& intervals) {
            ranges::sort(intervals);
            priority_queue<int,vector<int>,greater<>> q;
            
            for(auto t:intervals)
            {
                if(!q.empty() && q.top() < t[0]) q.pop();
                q.push(t[1]);
            }
            return q.size();
        }
    };
  

差分法

• 差分求最大值

•   class Solution {
    public:
        int minGroups(vector<vector<int>>& intervals) {
            map<int,int> diff;
            for(auto t:intervals)
                diff[t[0]] ++ , diff[t[1]+1] --;
            int res=0,sum=0;
            for(auto &[_,d]:diff)
                res = max(res,sum += d);
            return res;
        }
    };
  

原文地址：https://blog.csdn.net/Pisasama/article/details/140264020

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！