Back to Leetcode

Readme

Greedy/2580.Count-Ways-to-Group-Overlapping-Ranges/Readme.md

latest942 B
Original Source

2580.Count-Ways-to-Group-Overlapping-Ranges

对于区间类型的题目,最常见的处理手段就是将其排序。多数情况下,按照左端点排序就能解决很多问题。

我们考虑排序后的第一个区间范围是[l,r],我们只需要顺次往后遍历,就可以找到所有左端点小于等于r的区间。这些区间必然与第一个区间重合,它们必须归为一组。此时已经遍历过的这些区间,它们会有一个最远的右边界far,之后凡是左边界小于等于far的区间必然又会与这个组群有重叠。所以我们可以一路遍历下去:不断加入左边界小于等于far的区间,同时又更新far值变得更大。直至下一个区间的左边界大于far,说明之前的这些区间,必然有传递的交叠的关系,必须都归为一大组。

假设存在K个这样的大组,每个大组需要二选一站队,那么最终的答案就是2^N。