力扣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;
        }
    };