绿题大集合

题目条件

给定一些区间(n)的左右端点,在整数集合上进行覆盖。

【水题一】

双倍经验提交来这里。

求被覆盖次数不少于给定次数的段(定义为数轴上相邻两整数之间的距离为一段)有多少个。

解法一:

试图用map水过,map的建值对表示在当前值上被覆盖的次数,利用差分,实际是扫描线的思想在里面了,无需离散化。

map可以解决数组过大开不下的问题,当然前提是数组里有价值的信息只有那么几个。

复杂度:O(n)

解法二:

离散化,用线段树或是树状数组区修区询。有一点大材小用不动脑子的偷懒。

复杂度:O(nlogn)

【水题二】

求给定区间中被其他区间完全覆盖的区间有多少个。

解法一:

 

【水题三】

按照时间一个个覆盖,求能完全显示出来的区间有多少个。

【水题四】

实行区间并操作,升序输出区间的左右端点。

 

原文地址:https://www.cnblogs.com/ve-2021/p/10951941.html