Leetcode 2406

题目要求

给定一个闭区间[left, right]的序列，将其划分为多个不相交的分组，求最小的分组数

核心算法和原理

• 按照每个区间的左端点升序排列，然后从小到大遍历每个区间

• 用最小堆q动态维护已遍历区间的右端点
• 此时「将区间加入某分组」的做法即为「将分组的right替换为区间的right」
• 因为左端点是升序排列的，所以只寻找right最小的分组比较就行，该操作又可变成pop() + push(i的right)
• 对于区间i，当q为空或者i的left大于q的top（即当前区间与right最小的分组仍不相交）时，将该区间加入到分组中
• 否则，新建一个分组，push(i的right)

代码

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        // Build a small-root heap, maintain the smallest right top
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto& i : intervals) {
            if (!q.empty() && i[0] > q.top()) {
                q.pop();
            }
            q.push(i[1]);
        }
        return q.size();
    }
};