360提示危险的网站,大数据对网站建设教育的影响,泉州市第一建设有限公司网站,广西企业网站有哪些Acwing 906. 区间分组 知识点题目描述思路讲解代码展示 知识点
贪心
题目描述 思路讲解
这段代码是用来维护一个最小堆#xff0c;以确保右边界不相交的区间被正确地保留在堆中。让我详细解释这段代码#xff1a; heap.empty()#xff1a;这个条件检查最小堆 heap 是否为… Acwing 906. 区间分组 知识点题目描述思路讲解代码展示 知识点
贪心
题目描述 思路讲解
这段代码是用来维护一个最小堆以确保右边界不相交的区间被正确地保留在堆中。让我详细解释这段代码 heap.empty()这个条件检查最小堆 heap 是否为空。如果堆为空表示还没有存储任何右边界那么当前区间 r 的右边界 r.r 就会被直接添加到堆中。 heap.top() r.l这个条件检查当前堆中的最小右边界是否大于等于当前区间的左边界 r.l。如果最小右边界大于等于左边界表示当前区间与之前的区间有重叠或相交所以将当前区间的右边界 r.r 也加入堆中。 如果上述两个条件都不满足那么说明当前区间 r 的左边界 r.l 大于堆中的最小右边界这意味着当前区间与之前的区间不相交。在这种情况下我们可以将堆顶元素最小右边界弹出然后将当前区间的右边界 r.r 添加到堆中。这样做的目的是保持堆中的右边界尽量小以便后续区间能够更容易地与之前的区间不相交。
总之这段代码的作用是维护一个最小堆根据区间的左右边界来判断是否需要添加新的右边界到堆中以确保区间不相交的右边界被正确保留在堆中从而计算最少不相交子区间的数量。这是一个贪心算法的核心部分。
代码展示
#include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n;struct Range {int l, r;bool operator(const Range W) const {return l W.l;}
} range[N];int main() {scanf(%d, n);for (int i 0; i n; i) {int l, r;scanf(%d%d, l, r);range[i] {l, r};}sort(range, range n);priority_queueint, vectorint, greaterint heap; // 最小堆用来存储右边界堆顶是最小的for (int i 0; i n; i) {auto r range[i];if (heap.empty() || heap.top() r.l) heap.push(r.r);else {heap.pop();heap.push(r.r);}}printf(%d\n, heap.size());return 0;
}
