区间选点
算法步骤如下:
首先,先将区间按右端点从小到大排序
其次,从前往后枚举区间,判断当前选中的点ed与当前区间左端点的大小section[i].left。
若ed>=section[i].left,说明该点在当前区间内部,我们什么也不做
反之,需要重新选择点,即ed=section[i].right
最大不相交区间数量
对于这道题目,我们可以反向理解:如何表示相交区间?我们可以用一个点来表示相交的区间。每个集合中各个区间都至少有一点相交。若要选取不相交两个区间,那么两个区间必定处于不同的集合中,而最大的不相交区间数量便是总集合数,也就是区间选点的数量。因此该题的代码和区间选点的代码相同。
区间分组
将给定的若干个区间进行分组,使每一组中的区间之间没有交集,要求分组尽可能地少。
如何判断两个区间是否相交?
在区间按照左端点排序的情况下,我们只需要比较当前区间左端点的值和上一个区间右端点的值即可判断两区间是否相交。
由于题目要求的是最小组数,我们需要确保我们的代码能够 新建一个组, 比较当前区间和各个组的最右端点。
那么如何表示一个组?换句话说,我们可以用一个区间组的什么特点来表示组?
注意到我们最关心的是各个区间组的最右端点,因此我们可以利用每组的最右端点表示组。
到目前为止,我们已经知道了如何表示一个组。现在的问题是如何快速地判断是否需要新建一个组?换句话说,如何快速地比较当前区间和各个组的最右端点?假设每一个组的最右端点也按照从小到达的顺序排列,那么我们只需要比较当前区间的左端点和右端点最小值即可。如果区间左端点小于右端点最小值,那么说明当前区间与所有组都有交集,需要建立一个新组,反之就假如到最小右端点所对应的组当中,并且更新最小右端点。在实际的代码实现中,我们用堆来完成该步骤。
区间覆盖
给定N个闭区间与一个线段区间,选择尽量少的区间将指定线段区间完全覆盖。
要求选择尽可能少的区间,那么对于所选择的区间就有要求。
首先,区间的左端点必须小于等于线段区间的左端点(sec.left<=l);
其次,对于满足上述条件的区间,我们要选择右端点最大的区间。如果最大右端点是大于线段区间的左端点,那么我们依据该右端点值更新线段区间的左端点,反之不存在区间可以覆盖给定线段区间。如果我们不选择右端点最大的区间,那么就有可能增加选择区间的数量。
区间覆盖实现代码的一个错误
具体错误见打卡代码 https://www.acwing.com/activity/content/code/content/3944077/
这里解释一下为什么不能加 sec[j].right >= l
?
考虑这样一种情况,第一个区间是[-1,2],第二个区间[1,4],参考区间是[3,4]。如果加上上述条件,那么在执行第一次循环时就会令
flag = false
,从而导致错误的结果。