力扣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）！